动态规划：斐波那契数列

斐波那契数列是一个著名的数列，其中每个数字是前两个数字的和。例如，斐波那契数列的前几个数字是0、1、1、2、3、5、8、13等。
传统的递归方法可以很容易地解决斐波那契数列问题，但它的时间复杂度为O(2^n)，对于较大的n，效率非常低。为了更高效地求解斐波那契数列，我们可以使用动态规划。
动态规划的基本思想是将问题分解为子问题，并存储子问题的解，以便在需要时重复使用它们，而不是重新计算它们。对于斐波那契数列，我们可以创建一个数组dp，其中dp[i]表示第i个斐波那契数。然后，我们可以用以下方式填充dp数组：
dp[0] = 0
dp[1] = 1
对于i > 1，dp[i] = dp[i-1] + dp[i-2]
这样，我们只需要遍历数组一次就可以计算出前n个斐波那契数。这种方法的平均时间复杂度为O(n)，空间复杂度也为O(n)。
下面是一个Python代码实现：

def fibonacci(n):
if n <= 0:
return 0
elif n == 1:
return 1
else:
dp = [0, 1] + [0] * (n-1)  # 初始化dp数组
for i in range(2, n+1):
dp[i] = dp[i-1] + dp[i-2]  # 计算斐波那契数
return dp[-1]  # 返回第n个斐波那契数

使用示例：

print(fibonacci(10))  # 输出55，即前10个斐波那契数的最后一个数字

通过动态规划，我们可以更高效地求解斐波那契数列问题。这种方法不仅适用于斐波那契数列，也适用于其他许多递归问题。动态规划是一种强大的算法设计技术，可以帮助我们优化算法的性能。