二、知识总结

✨ 核心思想

动态规划（Dynamic Programming，简称 DP）是一种通过将复杂问题分解为更小的子问题来求解的算法思想。它的核心在于记录子问题的解，避免重复计算，从而提高效率。

动态规划适用于满足以下两个条件的问题：

• 最优子结构：问题的最优解可以由子问题的最优解推导而来
• 重叠子问题：在递归求解过程中，同一个子问题会被反复计算

✨ 动态规划的基本步骤

解决动态规划问题通常遵循以下步骤：

• 定义状态：明确 dp[i] 或 dp[i][j] 代表什么含义
• 推导状态转移方程：找出 dp[i] 与之前状态之间的递推关系
• 确定初始条件：设定边界值，作为递推的起点
• 确定计算顺序：通常从小问题向大问题推导（自底向上）
• 返回最终结果：根据状态定义，确定最终答案在 dp 数组中的位置

✨ 动态规划与其他方法的对比

动态规划与暴力枚举的区别：

• 暴力枚举会重复计算相同的子问题，时间复杂度通常较高
• 动态规划通过记忆化存储子问题的结果，避免重复计算

动态规划与贪心算法的区别：

• 贪心算法每一步都选择当前最优，不回头
• 动态规划会考虑所有可能的选择，通过比较得到全局最优解

动态规划与分治法的区别：

• 分治法将问题分解为互不重叠的子问题
• 动态规划处理的子问题之间存在重叠，因此需要记录中间结果

✨ 经典动态规划问题

以下是一些常见的动态规划问题类型：

• 线性 DP：最长上升子序列（LIS）、最长公共子序列（LCS）
• 背包问题：01背包、完全背包
• 区间 DP：合并石子、矩阵链乘法
• 网格 DP：方格取数、路径计数
• 字符串 DP：编辑距离、回文子串

在后续课程中，我们将逐一学习这些经典问题的解法。

✨ 执行示例

以斐波那契数列为例，展示动态规划的核心思想。

问题： 求第 n 个斐波那契数，F(0)=0, F(1)=1, F(n)=F(n-1)+F(n-2)。

暴力递归法（存在大量重复计算）：

1求 F(5) 的递归调用树：
2             F(5)
3           /      \
4        F(4)      F(3)
5       /    \    /    \
6     F(3)  F(2) F(2) F(1)
7    /   \
8  F(2) F(1)

可以看到 F(3) 被计算了 2 次，F(2) 被计算了 3 次。随着 n 增大，重复计算呈指数增长。

动态规划法（自底向上）：

每个子问题只计算一次，时间复杂度从指数级降为 O(n)。

✨ 解题步骤详解

用动态规划解题的通用流程（以爬楼梯问题为例）：

问题：每次可以爬 1 或 2 级台阶，爬到第 n 级有多少种方法？

1. 定义状态：dp[i] = 爬到第 i 级台阶的方法数
2. 推导状态转移方程：到达第 i 级，可以从第 i-1 级爬 1 步，或从第 i-2 级爬 2 步，所以 dp[i] = dp[i-1] + dp[i-2]
3. 确定初始条件：dp[1] = 1（1种方法），dp[2] = 2（2种方法）
4. 确定计算顺序：从 i=3 开始，依次计算到 i=n
5. 返回最终结果：dp[n]

1int climbStairs(int n) {
2    if (n <= 2) return n;
3    vector<int> dp(n + 1);
4    dp[1] = 1;
5    dp[2] = 2;
6    for (int i = 3; i <= n; i++) {
7        dp[i] = dp[i-1] + dp[i-2];
8    }
9    return dp[n];
10}

✨ 常见错误

1. 状态定义不清晰：在开始编码前，必须明确 dp[i] 的确切含义，模糊的定义会导致转移方程错误
2. 初始条件设置错误：边界值是整个递推的基础，初始值错了后面全部错
3. 计算顺序不对：计算 dp[i] 时必须保证它依赖的状态已经计算完成
4. 数组越界：在访问 dp[i-1] 或 dp[i-2] 时，要确保 i 足够大
5. 混淆子序列和子数组：子序列不要求连续，子数组要求连续，这两者的 DP 方程不同