04、动态规划基础知识
大约 14 分钟数据结构算法算法基地面试动态规划刷题程序厨校招社招
今天来给大家说一下什么是动态规划，这个文章写了挺长时间，大家可以详细的看一下，也看下是否有难以理解的地方，可以在文章中评论，我看到后会进行修改
什么是动态规划？
简单定义
动态规划（Dynamic Programming，简称 DP） 是一种通过把原问题分解为相对简单的子问题的方式来求解复杂问题的方法。
核心思想：
将一个复杂的问题分解成若干个子问题
保存子问题的解（避免重复计算）
通过子问题的解推导出原问题的解
简单来说：
记住已经解决过的子问题的答案
下次遇到相同的子问题，直接使用之前的答案
生活中的例子
例子 1：爬楼梯
问题：
你要爬 5 层楼梯，每次可以爬 1 层或 2 层
问：有多少种不同的爬法？
暴力思考：
列举所有可能的爬法
1+1+1+1+1
1+1+1+2
1+1+2+1
1+2+1+1
2+1+1+1
1+2+2
2+1+2
2+2+1
共 8 种
DP 思考：
要到第 5 层，可以从哪里来？
- 从第 4 层爬 1 层
- 从第 3 层爬 2 层
所以：
到第 5 层的方法数 = 到第 4 层的方法数 + 到第 3 层的方法数
递推关系：
f(5) = f(4) + f(3)
f(4) = f(3) + f(2)
f(3) = f(2) + f(1)
f(2) = 2（1+1 或 2）
f(1) = 1（只能 1）
计算：
f(1) = 1
f(2) = 2
f(3) = f(2) + f(1) = 2 + 1 = 3
f(4) = f(3) + f(2) = 3 + 2 = 5
f(5) = f(4) + f(3) = 5 + 3 = 8 ✓
这个后面会有相关题目
例子 2：零钱兑换
问题：
你有面值为 1 元、2 元、5 元的硬币若干
要凑出 11 元，最少需要几个硬币？
暴力思考：
尝试所有组合
11 = 1×11 （11 个）
11 = 1×9 + 2×1 （10 个）
11 = 1×7 + 2×2 （9 个）
...
11 = 1×1 + 5×2 （3 个）✓ 最少
太多了！
DP 思考：
要凑出 11 元，最后一个硬币可能是：
- 1 元：需要先凑出 10 元
- 2 元：需要先凑出 9 元
- 5 元：需要先凑出 6 元
所以：
凑 11 元 = 1 + min(凑 10 元, 凑 9 元, 凑 6 元)
递推关系：
f(11) = 1 + min(f(10), f(9), f(6))
计算过程：
f(0) = 0
f(1) = 1 （1×1）
f(2) = 1 （1×2）
f(3) = 2 （1×1 + 1×2）
f(4) = 2 （2×2）
f(5) = 1 （1×5）
f(6) = 2 （1×1 + 1×5）
f(7) = 2 （2×1 + 1×5）
f(8) = 3 （3×1 + 1×5 或 1×2 + 1×1 + 1×5）
f(9) = 3 （4×1 + 1×5 或 2×2 + 1×5）
f(10) = 2 （2×5）
f(11) = 1 + min(f(10), f(9), f(6))
= 1 + min(2, 3, 2)
= 3 ✓
答案：3 个硬币（1×1 + 2×5）
动态规划的核心特征
特征 1：最优子结构
定义：
问题的最优解包含子问题的最优解
通俗理解：
大问题的最优解可以由小问题的最优解推导出来
例子（爬楼梯）：
要用最优方法爬到第 5 层 = 最优地爬到第 4 层 + 爬 1 层 或 最优地爬到第 3 层 + 爬 2 层
如果到第 4 层的方法不是最优的
那到第 5 层的方法也不会是最优的
特征 2：重叠子问题
定义：
在求解过程中，会反复遇到相同的子问题
通俗理解：
同一个小问题会被计算多次
例子（斐波那契数列）：
计算 f(5) = f(4) + f(3)
计算 f(4) = f(3) + f(2)
注意：f(3) 被计算了 2 次！
递归树：
f(5)
/ \
f(4) f(3)
/ \ / \
f(3) f(2) f(2) f(1)
/ \ / \
f(2) f(1) f(1) f(0)
/ \
f(1) f(0)
f(3) 计算了 2 次
f(2) 计算了 3 次
f(1) 计算了 5 次
DP 的优势：
每个子问题只计算一次，保存结果
下次直接使用，避免重复计算
特征 3：无后效性
定义：
某个状态一旦确定，就不受之后决策的影响
通俗理解：
未来不会改变过去
例子（爬楼梯）：
到达第 3 层后，不管之后怎么爬
到第 3 层的方法数都不会改变
反例（不适合 DP）：
赌博问题：下一次的决策可能影响之前的收益
游戏中的悔棋：可以改变之前的状态
DP 的两种实现方式
方式 1：自顶向下（记忆化搜索）
思路：从原问题出发，递归求解子问题，用数组记录已计算的结果
特点：
- 思路自然，符合人的思维习惯
- 只计算需要的子问题
- 递归调用，可能栈溢出
- 有函数调用开销
代码示例（斐波那契）：
class Solution {
private:
vector<int> memo; // 记忆化数组
public:
int fib(int n) {
memo.resize(n + 1, -1); // 初始化为 -1（表示未计算）
return dp(n);
}
int dp(int n) {
// 基础情况
if (n == 0) {
return 0;
}
if (n == 1) {
return 1;
}
// 已经计算过，直接返回
if (memo[n] != -1) {
return memo[n];
}
// 递归计算并保存结果
memo[n] = dp(n - 1) + dp(n - 2);
return memo[n];
}
};
方式 2：自底向上（递推）
思路：从最小的子问题开始，逐步推导到原问题
特点：
- 没有递归，不会栈溢出
- 效率更高（无函数调用开销）
- 空间可以优化
需要考虑计算顺序
代码示例（斐波那契）：
class Solution {
public:
int fib(int n) {
if (n == 0) {
return 0;
}
if (n == 1) {
return 1;
}
// dp[i] 表示第 i 个斐波那契数
vector<int> dp(n + 1);
// 基础情况
dp[0] = 0;
dp[1] = 1;
// 从小到大递推
for (int i = 2; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
};
执行过程：
计算 fib(5)
初始化：
dp[0] = 0
dp[1] = 1
递推：
i=2: dp[2] = dp[1] + dp[0] = 1 + 0 = 1
i=3: dp[3] = dp[2] + dp[1] = 1 + 1 = 2
i=4: dp[4] = dp[3] + dp[2] = 2 + 1 = 3
i=5: dp[5] = dp[4] + dp[3] = 3 + 2 = 5 ✓
dp 数组：[0, 1, 1, 2, 3, 5]
下面的内容是动态规划，最重要的地方，大家可以认真看一下并自行思考和总结
DP 解题五部曲
步骤 1：确定 dp 数组及下标含义
明确定义：
dp[i] 表示什么？
dp[i][j] 表示什么？
常见定义（现在不懂没事，后面的题目会用到）：
- dp[i]：到达位置 i 时的最优解
- dp[i]：前 i 个元素的最优解
- dp[i][j]：从 i 到 j 的最优解
- dp[i][0/1]：第 i 个位置的某种状态
例子（爬楼梯）：
dp[i] 表示爬到第 i 层楼梯的方法数
例子（零钱兑换）：
dp[i] 表示凑出金额 i 所需的最少硬币数
例子（买卖股票）：
dp[i][0] 表示第 i 天不持有股票的最大利润
dp[i][1] 表示第 i 天持有股票的最大利润
步骤 2：确定递推公式
找规律：
当前状态如何从之前的状态推导出来？
常见模式：
- 选或不选：dp[i] = max(选, 不选)
- 路径问题：dp[i] = dp[前一个位置] + 当前值
- 背包问题：dp[i][j] = max(放, 不放)
例子（爬楼梯）：
dp[i] = dp[i-1] + dp[i-2]
（从 i-1 爬 1 层，或从 i-2 爬 2 层）
例子（最小路径和）：
dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])
（只能从上方或左方来）
例子（打家劫舍）：
dp[i] = max(dp[i-1], dp[i-2] + nums[i])
（不偷第 i 家，或偷第 i 家）
步骤 3：dp 数组如何初始化
确定边界：
最小的子问题的答案是什么？
常见初始化：
- dp[0] = ...（第 0 个位置）
- dp[i][0] = ...（第一列）
- dp[0][j] = ...（第一行）
例子（爬楼梯）：
dp[0] = 1 // 不爬也算一种方法
dp[1] = 1 // 只有一种方法
例子（零钱兑换）：
dp[0] = 0 // 凑 0 元需要 0 个硬币
例子（最小路径和）：
dp[0][0] = grid[0][0] // 起点
第一行：只能从左边来
第一列：只能从上边来
步骤 4：确定遍历顺序
关键问题：
先计算哪个，后计算哪个？
常见顺序：
- 一维 DP：从小到大遍历
- 二维 DP：
- 按行遍历：i 从小到大，j 从小到大
- 按对角线遍历
- 按长度遍历
判断依据：
看递推公式依赖哪些状态
被依赖的状态要先计算
例子（爬楼梯）：
dp[i] = dp[i-1] + dp[i-2]
依赖 i-1 和 i-2
所以从小到大遍历
例子（最长回文子串）：
dp[i][j] 依赖 dp[i+1][j-1]
需要先计算内层，再计算外层
所以按长度从小到大遍历
步骤 5：举例推导 dp 数组
重要性：
写完代码后，手动推导一个例子
验证 dp 数组的值是否符合预期
推导过程：
1. 选一个简单的测试用例
2. 手动计算每一步的 dp 值
3. 对比代码输出的 dp 数组
4. 如果不一致，找出错误
例子（爬楼梯，n=5）：
dp[0] = 1
dp[1] = 1
dp[2] = dp[1] + dp[0] = 1 + 1 = 2
dp[3] = dp[2] + dp[1] = 2 + 1 = 3
dp[4] = dp[3] + dp[2] = 3 + 2 = 5
dp[5] = dp[4] + dp[3] = 5 + 3 = 8 ✓
如果 dp[5] != 8，说明代码有问题
经典 DP 问题分类
类型 1：线性 DP（一维）
特点：状态只依赖前面的若干个状态
1.1 爬楼梯类
代表题目：
- LeetCode 70. 爬楼梯
- LeetCode 746. 使用最小花费爬楼梯
特征：
- 每次可以前进固定的步数
- 求方案数或最小代价
递推公式：
dp[i] = dp[i-1] + dp[i-2] + ...
1.2 打家劫舍类
代表题目：
- LeetCode 198. 打家劫舍
- LeetCode 213. 打家劫舍 II
特征：
- 不能选择相邻的元素
- 求最大收益
递推公式：
dp[i] = max(dp[i-1], dp[i-2] + nums[i])
1.3 买卖股票类
代表题目：
- LeetCode 121. 买卖股票的最佳时机
- LeetCode 122. 买卖股票的最佳时机 II
特征：
- 有买入、卖出、持有等多种状态
- 求最大利润
递推公式：
dp[i][0] = max(dp[i-1][0], dp[i-1][1] + price)
dp[i][1] = max(dp[i-1][1], -price)
类型 2：线性 DP（二维）
特点：状态由两个维度决定
2.1 路径问题
代表题目：
- LeetCode 62. 不同路径
- LeetCode 63. 不同路径 II
- LeetCode 64. 最小路径和
特征：
- 在网格中移动
- 只能向右或向下
递推公式：
dp[i][j] = dp[i-1][j] + dp[i][j-1]
2.2 编辑距离类
代表题目：
- LeetCode 72. 编辑距离
- LeetCode 1143. 最长公共子序列
特征：
- 字符串匹配
- 需要考虑插入、删除、替换
递推公式：
if (s1[i] == s2[j]):
dp[i][j] = dp[i-1][j-1]
else:
dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
类型 3：背包问题
特点：选择物品，满足约束条件
3.1 0-1 背包
代表题目：
- LeetCode 416. 分割等和子集
特征：
- 每个物品只能选一次
- 有容量限制
递推公式：
dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])
3.2 完全背包
代表题目：
- LeetCode 322. 零钱兑换
- LeetCode 518. 零钱兑换 II
特征：
- 每个物品可以选无限次
- 有容量限制
递推公式：
dp[j] = min(dp[j], dp[j-coin] + 1)
类型 4：区间 DP
特点：在一个区间上定义状态
代表题目：
- LeetCode 5. 最长回文子串
- LeetCode 516. 最长回文子序列
特征：
- dp[i][j] 表示区间 [i, j] 的答案
- 通常按区间长度从小到大遍历
递推公式：
dp[i][j] = dp[i+1][j-1] + ...
类型 5：树形 DP
特点：在树结构上定义状态
代表题目：
- LeetCode 337. 打家劫舍 III
特征：
- 在树的节点上定义状态
- 通常用 DFS 实现
递推公式：
选当前节点：val + 不选子节点
不选当前节点：max(选/不选左子节点) + max(选/不选右子节点)
如何判断一道题能用 DP（很多时候，我们并知道这个题目可以用 dp 来解答）
判断标准
可以用 DP 的信号：
1. 求最优解（最大值、最小值、最长、最短）
- 最大利润
- 最小代价
- 最长子序列
2. 求方案数
- 有多少种方法
- 有多少种组合
3. 求可行性
- 能否达到某个目标
- 能否分割成若干部分
4. 问题可以分解成子问题
- 大问题依赖小问题
- 小问题的解可以推导出大问题的解
5. 有重叠子问题
- 暴力递归会计算很多重复的子问题
典型关键词
看到以下关键词，考虑 DP：
最大、最小 → 最大利润、最小花费
最长、最短 → 最长子序列、最短路径
有多少种方法 → 爬楼梯、组合总和
能否、是否 → 能否分割、是否可达
一些限制条件 → 不能相邻、最多 k 次
练习建议
下面这些题目建议大家必做哈
入门题目
1. LeetCode 509. 斐波那契数
- 最基础的 DP
- 理解记忆化和递推
2. LeetCode 70. 爬楼梯
- 经典入门题
- 理解状态转移
3. LeetCode 746. 使用最小花费爬楼梯
- 增加了代价概念
- 练习初始化
4. LeetCode 198. 打家劫舍
- "选或不选"模式
- 理解状态定义
5. LeetCode 121. 买卖股票的最佳时机
- 一维 DP 或贪心
- 简单但巧妙
进阶题目
6. LeetCode 64. 最小路径和
- 二维 DP 入门
- 路径问题
7. LeetCode 5. 最长回文子串
- 区间 DP
- 中心扩散
8. LeetCode 322. 零钱兑换
- 完全背包
- 经典模型
9. LeetCode 416. 分割等和子集
- 0-1 背包
- 转化思维
10. LeetCode 1143. 最长公共子序列
- 二维 DP
- 字符串问题
给大家整理了一些常用的 dp 模板，但是不一定能够
常用 DP 模板
模板 1：一维 DP
// 问题：求某个位置的最优解
int solve(vector<int>& nums) {
int n = nums.size();
vector<int> dp(n);
// 初始化
dp[0] = ...;
// 递推
for (int i = 1; i < n; i++) {
dp[i] = ... // 根据 dp[i-1], dp[i-2] 等推导
}
return dp[n-1];
}
模板 2：二维 DP
// 问题：二维网格或两个序列
int solve(vector<vector<int>>& grid) {
int m = grid.size();
int n = grid[0].size();
vector<vector<int>> dp(m, vector<int>(n));
// 初始化
dp[0][0] = ...;
// 初始化第一行和第一列
// 递推
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
dp[i][j] = ... // 根据 dp[i-1][j], dp[i][j-1] 等推导
}
}
return dp[m-1][n-1];
}
模板 3：背包问题
// 0-1 背包
int knapsack(vector<int>& weights, vector<int>& values, int capacity) {
vector<int> dp(capacity + 1, 0);
for (int i = 0; i < weights.size(); i++) {
// 从右往左遍历（避免重复选择）
for (int j = capacity; j >= weights[i]; j--) {
dp[j] = max(dp[j], dp[j - weights[i]] + values[i]);
}
}
return dp[capacity];
}
// 完全背包
int knapsackComplete(vector<int>& weights, vector<int>& values, int capacity) {
vector<int> dp(capacity + 1, 0);
for (int i = 0; i < weights.size(); i++) {
// 从左往右遍历（允许重复选择）
for (int j = weights[i]; j <= capacity; j++) {
dp[j] = max(dp[j], dp[j - weights[i]] + values[i]);
}
}
return dp[capacity];
}
