动态规划实现斐波那契数列

动态规划实现斐波那契数列可以通过定义一个数组来存储计算过程中的中间结果，从而避免重复计算。具体实现如下：

def fibonacci(n):
    if n <= 1:
        return n
    fib = [0] * (n+1)
    fib[1] = 1
    for i in range(2, n+1):
        fib[i] = fib[i-1] + fib[i-2]
    return fib[n]

这里定义了一个长度为 n+1 的数组 fib，其中 fib[i] 表示第 i 个斐波那契数列的值。初始化 fib[1] 为 1，然后从第 2 个位置开始，通过 fib[i-1] 和 fib[i-2] 的值计算出 fib[i] 的值，避免了重复计算。

这样的时间复杂度为 O(n)，空间复杂度为 O(n)。如果只需要计算一个斐波那契数列的值，可以将空间复杂度优化为 O(1)。