动态规划教程

动态规划（Dynamic Programming，简称 DP）是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。

动态规划的特点

最优子结构：一个问题的最优解包含其子问题的最优解。
子问题重叠：不同的问题会包含相同的子问题。
无后效性：一个给定问题的子问题解不会受后续子问题解的影响。

动态规划的应用

动态规划广泛应用于算法设计中，如：

背包问题
最长公共子序列
最长递增子序列
矩阵链乘
斐波那契数列

例子：斐波那契数列

斐波那契数列（Fibonacci sequence）是一个著名的序列，其递推公式为：F(n) = F(n-1) + F(n-2)，其中 F(0) = 0, F(1) = 1。

以下是一个使用动态规划求解斐波那契数列的示例：

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

print(fibonacci(10))  # 输出 55

更多关于动态规划的内容，您可以访问我们的动态规划教程页面。