动态规划（Dynamic Programming）

动态规划（DP）是解决最优化问题的算法策略之一。它通过将复杂问题分解为更小的子问题，并存储这些子问题的解，从而避免重复计算。

基本概念

• 最优子结构：一个问题的最优解包含其子问题的最优解。
• 重叠子问题：不同的问题实例共享子问题。
• 子问题重叠：子问题被重复计算。

常见问题类型

1. 最短路径问题：如 Dijkstra 算法、Floyd 算法。
2. 背包问题：如 0/1 背包问题、完全背包问题。
3. 最长子序列问题：如最长公共子序列。

实例分析

以下是一个简单的 DP 例子：计算斐波那契数列。

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

学习资源

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

动态规划示例