第 9 章 动态规划基础¶
动态规划（Dynamic Programming，简称 DP） 是算法竞赛中最核心、最高频的专题之一。掌握 DP 的关键不在于记住模板，而在于学会定义状态和推导转移方程的思维方法。
9.1 什么是动态规划¶
动态规划是一种通过把原问题分解为相对简单的子问题的方式来求解复杂问题的方法。与分治法不同的是，DP 的子问题往往是重叠的——同一个子问题会被反复求解。DP 通过记忆化的方式，保证每个子问题只被计算一次。
一个能用动态规划求解的问题，必须满足以下三个性质：
9.1.1 最优子结构（Optimal Substructure）¶
问题的最优解包含其子问题的最优解。换句话说，我们可以通过组合子问题的最优解来构造原问题的最优解。
例子：最短路径
从 A 到 C 的最短路径经过 B，那么 A→B 段和 B→C 段也一定分别是各自的最短路径。这就是最优子结构。
9.1.2 无后效性（No Aftereffect）¶
一旦某个状态确定，它此后的变化只与当前状态有关，与到达这个状态的路径无关。
例子：棋盘走法
当我们站在棋盘上某个格子 (i, j) 时，之后能怎么走只取决于当前位置，而不关心我们是经过哪些格子到达 (i, j) 的。
9.1.3 重叠子问题（Overlapping Subproblems）¶
在递归求解过程中，同一个子问题会被多次计算。
graph TD
A["f(5)"] --> B["f(4)"]
A --> C["f(3)"]
B --> D["f(3)"]
B --> E["f(2)"]
C --> F["f(2)"]
C --> G["f(1)"]
D --> H["f(2)"]
D --> I["f(1)"]
style D fill:#ff9999,stroke:#cc0000
style F fill:#ff9999,stroke:#cc0000
style H fill:#ff9999,stroke:#cc0000
style E fill:#99ccff,stroke:#0066cc上图中，红色节点
f(3)和f(2)被重复计算了多次。动态规划通过记忆化将这些重复计算消除。
区分 DP 与贪心
贪心算法也利用最优子结构，但贪心每一步只看当前最优，不回溯。DP 则会综合考虑所有子问题的解。贪心问题往往也可以用 DP 求解（但代价更高），DP 适用面更广。
9.2 DP 的解题步骤¶
求解 DP 问题有一套通用的思维框架，建议初学者严格按以下「四步 + 输出答案」的流程走：
graph LR
A["① 定义状态"] --> B["② 写转移方程"]
B --> C["③ 确定初始条件和边界"]
C --> D["④ 确定计算顺序"]
D --> E["⑤ 输出答案"]第一步：定义状态¶
状态是 DP 的灵魂。定义 dp[i] 或 dp[i][j] 代表什么，直接决定了问题能否解出来。
状态定义技巧
- 一维不够就加维度，但维度越多复杂度越高
- 状态的值通常表示：方案数、最值（最大/最小）、是否存在
- 问什么就让
dp[...]表示什么
第二步：写转移方程¶
思考「最后一步」——当前状态可以从哪些前驱状态转移过来，转移的代价/收益是什么。
第三步：确定初始条件和边界¶
递推需要有「起点」，即最简单情况下的答案。同时注意数组越界等边界问题。
第四步：确定计算顺序¶
保证在计算 dp[i] 时，它所依赖的状态都已经计算完毕。
9.3 记忆化搜索 vs 递推¶
DP 有两种实现方式：
| 对比维度 | 记忆化搜索（自顶向下） | 递推（自底向上） |
|---|---|---|
| 思路 | 从目标问题出发，递归分解 | 从最小子问题出发，逐步递推 |
| 实现 | 递归 + 数组记录已算结果 | 嵌套循环填充 dp 数组 |
| 优点 | 思路自然，不需要考虑计算顺序 | 无递归开销，容易空间优化 |
| 缺点 | 递归栈开销，可能爆栈 | 需要手动确定计算顺序 |
| 适用 | 状态转移复杂、计算顺序难确定 | 状态转移清晰、需要空间优化 |
示例：爬楼梯（LC 70）¶
问题：每次可以上 1 阶或 2 阶，求上 n 阶楼梯有多少种方案。
记忆化搜索写法：
#include <bits/stdc++.h>
using namespace std;
int memo[50]; // 记忆化数组（注意：n≥46 时斐波那契数超出 int 范围，此处仅示教；实战用 long long）
// 从第 i 阶出发，到达第 n 阶的方案数
int dfs(int i, int n) {
if (i > n) return 0; // 超出范围，不合法
if (i == n) return 1; // 到达终点，方案数为 1
if (memo[i] != -1) return memo[i]; // 已经算过了，直接返回
// 可以走 1 步或 2 步
return memo[i] = dfs(i + 1, n) + dfs(i + 2, n);
}
int main() {
int n;
cin >> n;
memset(memo, -1, sizeof(memo));
cout << dfs(0, n) << endl;
return 0;
}
递推写法：
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
vector<int> dp(n + 1, 0);
dp[0] = 1; // 初始条件：站在地面，有 1 种方案
dp[1] = 1; // 1 阶楼梯，只能走 1 步
for (int i = 2; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2]; // 转移方程
}
cout << dp[n] << endl;
return 0;
}
复杂度分析：
| 方式 | 时间复杂度 | 空间复杂度 |
|---|---|---|
| 记忆化搜索 | O(n) | O(n)（递归栈 + 记忆数组） |
| 递推 | O(n) | O(n)（可优化到 O(1)，见下文） |
graph LR
subgraph 记忆化搜索
A1["dfs(0)"] --> A2["dfs(1)"]
A1 --> A3["dfs(2)"]
A2 --> A3
A2 --> A4["dfs(3)"]
A3 --> A4
A3 --> A5["dfs(4)"]
end
subgraph 递推
B1["dp[0]=1"] --> B2["dp[1]=1"]
B2 --> B3["dp[2]=2"]
B3 --> B4["dp[3]=3"]
B4 --> B5["dp[4]=5"]
end如何选择
- 如果你对递推的计算顺序没把握，先用记忆化搜索写，不容易出错
- 如果需要空间优化（如滚动数组），只能用递推
- 竞赛中两者都可以，选自己写得快、写得对的
9.4 线性 DP¶
线性 DP 是指状态沿着一维或多维线性结构递推的问题，是最基础也最常见的 DP 类型。
9.4.1 爬楼梯（LC 70）¶
已在 9.3 中详细讲解，此处补充空间优化版本：
// 空间优化：只用两个变量
int climbStairs(int n) {
if (n <= 2) return n;
int prev2 = 1, prev1 = 2; // dp[i-2], dp[i-1]
for (int i = 3; i <= n; i++) {
int curr = prev1 + prev2;
prev2 = prev1;
prev1 = curr;
}
return prev1;
}
- 时间复杂度：O(n)
- 空间复杂度：O(1)
9.4.2 打家劫舍（LC 198）¶
问题：一排房屋中存放了不同金额的钱，不能同时抢劫相邻的两间房屋，求能抢到的最大金额。
状态定义：dp[i] = 前 i 间房屋能抢到的最大金额
转移方程：
\[dp[i] = \max(dp[i-1], \; dp[i-2] + nums[i])\]
dp[i-1]：不抢第 i 间，沿用前 i-1 间的最优解dp[i-2] + nums[i]：抢第 i 间，则第 i-1 间不能抢
graph LR
subgraph "房屋 0-4"
H0["🏠 0: 2元"] --- H1["🏠 1: 7元"] --- H2["🏠 2: 9元"] --- H3["🏠 3: 3元"] --- H4["🏠 4: 1元"]
end
style H0 fill:#90EE90
style H2 fill:#90EE90
style H4 fill:#90EE90
style H1 fill:#FFB6C1
style H3 fill:#FFB6C1最优方案：抢第 0、2、4 间 = 2 + 9 + 1 = 12
#include <bits/stdc++.h>
using namespace std;
int rob(vector<int>& nums) {
int n = nums.size();
if (n == 1) return nums[0];
vector<int> dp(n, 0);
dp[0] = nums[0];
dp[1] = max(nums[0], nums[1]);
for (int i = 2; i < n; i++) {
dp[i] = max(dp[i - 1], dp[i - 2] + nums[i]);
}
return dp[n - 1];
}
空间优化：
int rob(vector<int>& nums) {
int n = nums.size();
if (n == 1) return nums[0];
int prev2 = nums[0], prev1 = max(nums[0], nums[1]);
for (int i = 2; i < n; i++) {
int curr = max(prev1, prev2 + nums[i]);
prev2 = prev1;
prev1 = curr;
}
return prev1;
}
- 时间复杂度：O(n)
- 空间复杂度：O(1)（优化后）
9.4.3 打家劫舍 II（LC 213）¶
问题：房屋围成一圈，首尾相邻，不能同时抢劫首尾两间。
思路：由于首尾不能同时选，分两种情况取最大值：
- 抢第 0 间到第 n-2 间（不抢最后一间）
- 抢第 1 间到第 n-1 间（不抢第一间）
#include <bits/stdc++.h>
using namespace std;
// 辅助函数：计算线性情况 [start, end] 的最大抢劫金额
int robRange(vector<int>& nums, int start, int end) {
int prev2 = 0, prev1 = 0;
for (int i = start; i <= end; i++) {
int curr = max(prev1, prev2 + nums[i]);
prev2 = prev1;
prev1 = curr;
}
return prev1;
}
int rob(vector<int>& nums) {
int n = nums.size();
if (n == 1) return nums[0];
if (n == 2) return max(nums[0], nums[1]);
// 情况 1：不抢最后一间 | 情况 2：不抢第一间
return max(robRange(nums, 0, n - 2), robRange(nums, 1, n - 1));
}
- 时间复杂度：O(n)
- 空间复杂度：O(1)
graph TD
A["环形房屋问题"] --> B["情况1: 不选最后一间"]
A --> C["情况2: 不选第一间"]
B --> D["线性打家劫舍 [0, n-2]"]
C --> E["线性打家劫舍 [1, n-1]"]
D --> F["取两者最大值"]
E --> F9.4.4 最长递增子序列 LIS（LC 300）¶
问题：给定一个整数数组，找到其中最长严格递增子序列的长度。
状态定义：dp[i] = 以 nums[i] 结尾的最长递增子序列长度
转移方程：
\[dp[i] = \max(dp[j] + 1) \quad \text{其中 } 0 \le j < i \text{ 且 } nums[j] < nums[i]\]
graph TD
subgraph "数组: [10, 9, 2, 5, 3, 7, 101, 18]"
A["nums[0]=10, dp[0]=1"]
B["nums[1]=9, dp[1]=1"]
C["nums[2]=2, dp[2]=1"]
D["nums[3]=5, dp[3]=dp[2]+1=2"]
E["nums[4]=3, dp[4]=dp[2]+1=2"]
F["nums[5]=7, dp[5]=dp[3]+1=3"]
G["nums[6]=101, dp[6]=dp[5]+1=4"]
H["nums[7]=18, dp[7]=dp[5]+1=4"]
end最长递增子序列长度 = 4（如
2, 3, 7, 18或2, 5, 7, 101）
朴素 O(n²) 解法：
#include <bits/stdc++.h>
using namespace std;
int lengthOfLIS(vector<int>& nums) {
int n = nums.size();
vector<int> dp(n, 1); // 每个元素自身就是一个长度为 1 的子序列
int ans = 1;
for (int i = 1; i < n; i++) {
for (int j = 0; j < i; j++) {
if (nums[j] < nums[i]) {
dp[i] = max(dp[i], dp[j] + 1);
}
}
ans = max(ans, dp[i]);
}
return ans;
}
- 时间复杂度：O(n²)
- 空间复杂度：O(n)
贪心 + 二分 O(n log n) 优化：
维护一个辅助数组 tail，tail[len] 表示长度为 len 的递增子序列的最小末尾元素。
#include <bits/stdc++.h>
using namespace std;
int lengthOfLIS(vector<int>& nums) {
vector<int> tail; // tail[i] = 长度为 i+1 的 LIS 的最小末尾
for (int x : nums) {
// 在 tail 中找第一个 >= x 的位置
auto it = lower_bound(tail.begin(), tail.end(), x);
if (it == tail.end()) {
tail.push_back(x); // x 比所有元素都大，延长 LIS
} else {
*it = x; // 替换，保持末尾尽可能小
}
}
return tail.size();
}
- 时间复杂度：O(n log n)
- 空间复杂度：O(n)
为什么 tail 数组是正确的？
tail 数组始终保持递增性质。对于长度相同的子序列，末尾元素越小越好——因为它更有可能被后面的元素接上，形成更长的子序列。
9.4.5 最长公共子序列 LCS¶
问题：给定两个字符串 text1 和 text2，找出它们的最长公共子序列的长度。
状态定义：dp[i][j] = text1 的前 i 个字符与 text2 的前 j 个字符的 LCS 长度
转移方程：
\[dp[i][j] = \begin{cases} dp[i-1][j-1] + 1 & \text{if } text1[i-1] = text2[j-1] \\ \max(dp[i-1][j], \; dp[i][j-1]) & \text{otherwise} \end{cases}\]
graph TD
subgraph "text1 = 'abcde', text2 = 'ace'"
A["比较 text1[i] 和 text2[j]"]
A -->|"相等"| B["dp[i][j] = dp[i-1][j-1] + 1"]
A -->|"不等"| C["dp[i][j] = max(dp[i-1][j], dp[i][j-1])"]
endDP 表格示意（text1 = "abcde", text2 = "ace"）：
| "" | a | c | e | |
|---|---|---|---|---|
| "" | 0 | 0 | 0 | 0 |
| a | 0 | 1 | 1 | 1 |
| b | 0 | 1 | 1 | 1 |
| c | 0 | 1 | 2 | 2 |
| d | 0 | 1 | 2 | 2 |
| e | 0 | 1 | 2 | 3 |
LCS = "ace"，长度为 3
#include <bits/stdc++.h>
using namespace std;
int longestCommonSubsequence(string text1, string text2) {
int m = text1.size(), n = text2.size();
vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (text1[i - 1] == text2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
return dp[m][n];
}
- 时间复杂度：O(m × n)
- 空间复杂度：O(m × n)（可优化到 O(min(m, n))）
9.4.6 编辑距离（LC 72）¶
问题：将字符串 word1 转换成 word2 所需的最少操作数。允许的操作：插入、删除、替换一个字符。
状态定义：dp[i][j] = 将 word1 的前 i 个字符转换为 word2 的前 j 个字符所需的最少操作数
转移方程：
\[dp[i][j] = \begin{cases} dp[i-1][j-1] & \text{if } word1[i-1] = word2[j-1] \\ 1 + \min \begin{cases} dp[i-1][j] & \text{（删除）} \\ dp[i][j-1] & \text{（插入）} \\ dp[i-1][j-1] & \text{（替换）} \end{cases} & \text{otherwise} \end{cases}\]
graph TD
A["dp[i][j]"] --> B{"word1[i-1] == word2[j-1] ?"}
B -->|"是"| C["dp[i][j] = dp[i-1][j-1]"]
B -->|"否"| D["取三种操作的最小值"]
D --> E["删除: dp[i-1][j] + 1"]
D --> F["插入: dp[i][j-1] + 1"]
D --> G["替换: dp[i-1][j-1] + 1"]#include <bits/stdc++.h>
using namespace std;
int minDistance(string word1, string word2) {
int m = word1.size(), n = word2.size();
vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
// 初始条件：空串到目标串需要的插入操作
for (int i = 0; i <= m; i++) dp[i][0] = i; // 全部删除
for (int j = 0; j <= n; j++) dp[0][j] = j; // 全部插入
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (word1[i - 1] == word2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1]; // 字符相同，不需要操作
} else {
dp[i][j] = 1 + min({
dp[i - 1][j], // 删除 word1[i-1]
dp[i][j - 1], // 插入 word2[j-1]
dp[i - 1][j - 1] // 替换 word1[i-1] 为 word2[j-1]
});
}
}
}
return dp[m][n];
}
DP 表格示意（word1 = "horse", word2 = "ros"）：
| "" | r | o | s | |
|---|---|---|---|---|
| "" | 0 | 1 | 2 | 3 |
| h | 1 | 1 | 2 | 3 |
| o | 2 | 2 | 1 | 2 |
| r | 3 | 2 | 2 | 2 |
| s | 4 | 3 | 3 | 2 |
| e | 5 | 4 | 4 | 3 |
- 时间复杂度：O(m × n)
- 空间复杂度：O(m × n)
9.4.7 最大子数组和（LC 53）¶
问题：找到一个具有最大和的连续子数组，返回其最大和。
状态定义：dp[i] = 以 nums[i] 结尾的最大子数组和
转移方程：
\[dp[i] = \max(nums[i], \; dp[i-1] + nums[i])\]
含义：要么从 nums[i] 重新开始一个子数组，要么把 nums[i] 接到前面的子数组后面。
graph LR
A["nums = [-2,1,-3,4,-1,2,1,-5,4]"]
B["dp = [-2,1,-2,4,3,5,6,1,5]"]
C["答案 = max(dp) = 6"]
A --> B --> C#include <bits/stdc++.h>
using namespace std;
int maxSubArray(vector<int>& nums) {
int n = nums.size();
int cur = nums[0]; // 当前以 i 结尾的最大子数组和
int ans = nums[0]; // 全局最大值
for (int i = 1; i < n; i++) {
cur = max(nums[i], cur + nums[i]); // 转移
ans = max(ans, cur); // 更新答案
}
return ans;
}
- 时间复杂度：O(n)
- 空间复杂度：O(1)
Kadane 算法
最大子数组和的 DP 解法也被称为 Kadane 算法，是线性 DP 中最经典的例子之一。
9.5 网格路径 DP¶
网格路径 DP 是线性 DP 向二维的自然推广：在一个 m×n 的网格上，从左上角出发，每步只能向右或向下走一格，走到右下角。状态天然定义为 dp[i][j]（走到格子 (i, j) 时的答案），转移只来自上方和左方两个前驱。它是很多二维 DP 问题（带障碍路径、地下城游戏、三角形最小路径和等）的基础模型，是入门必会内容。
graph TD
A["dp[i][j]"] --> B["前驱 1: 上方 dp[i-1][j]"]
A --> C["前驱 2: 左方 dp[i][j-1]"]
B --> D["求方案数: 两者相加 / 求最值: 两者取 min 或 max"]
C --> D9.5.1 不同路径（LC 62）¶
问题：机器人位于 m×n 网格的左上角，每次只能向右或向下移动一步，问到达右下角共有多少条不同的路径。
按四步法分析：
- 状态定义：
dp[i][j]= 从起点(0, 0)走到(i, j)的路径数 - 转移方程：\(dp[i][j] = dp[i-1][j] + dp[i][j-1]\)（最后一步要么从上方来，要么从左方来，两类路径互不重叠）
- 初始条件：第一行、第一列都只有 1 条路径（只能一路向右 / 一路向下）
- 计算顺序：逐行、每行从左到右，保证上方和左方先算好
DP 表格示意（m = 3, n = 7）：
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | |
|---|---|---|---|---|---|---|---|
| 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 1 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| 2 | 1 | 3 | 6 | 10 | 15 | 21 | 28 |
m = 3, n = 7 时答案为 28。
#include <bits/stdc++.h>
using namespace std;
int uniquePaths(int m, int n) {
// dp[i][j] = 到达 (i, j) 的路径数
vector<vector<int>> dp(m, vector<int>(n, 0));
for (int i = 0; i < m; i++) dp[i][0] = 1; // 第一列只能一路向下
for (int j = 0; j < n; j++) dp[0][j] = 1; // 第一行只能一路向右
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];
}
滚动数组优化：dp[i][j] 只依赖上一行的 dp[i-1][j] 与本行的 dp[i][j-1]，可以压缩为一维——更新 dp[j] 时，dp[j] 的旧值恰好是上方，dp[j-1] 的新值恰好是左方：
int uniquePaths(int m, int n) {
vector<int> dp(n, 1); // 第 0 行全为 1
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
dp[j] += dp[j - 1]; // dp[j]（旧值=上方）+ dp[j-1]（新值=左方）
}
}
return dp[n - 1];
}
- 时间复杂度：O(m × n)
- 空间复杂度：O(m × n)，滚动数组优化后 O(n)
9.5.2 最小路径和（LC 64）¶
问题：给定一个包含非负整数的 m×n 网格 grid，从左上角走到右下角，每次只能向右或向下移动一步，求路径上数字总和的最小值。
状态定义：dp[i][j] = 从 (0, 0) 走到 (i, j) 的最小路径和
转移方程：
\[dp[i][j] = \min(dp[i-1][j], \; dp[i][j-1]) + grid[i][j]\]
与「不同路径」相比只有一处变化：方案数的「相加」换成了最值的「取 min」。
DP 表格示意（grid = [[1,3,1],[1,5,1],[4,2,1]]）：
| dp | 列 0 | 列 1 | 列 2 |
|---|---|---|---|
| 行 0 | 1 | 4 | 5 |
| 行 1 | 2 | 7 | 6 |
| 行 2 | 6 | 8 | 7 |
最优路径 1 → 3 → 1 → 1 → 1，总和 7。
#include <bits/stdc++.h>
using namespace std;
int minPathSum(vector<vector<int>>& grid) {
int m = grid.size(), n = grid[0].size();
vector<vector<int>> dp(m, vector<int>(n, 0));
dp[0][0] = grid[0][0];
// 边界：第一列只能从上方来，第一行只能从左方来
for (int i = 1; i < m; i++) dp[i][0] = dp[i - 1][0] + grid[i][0];
for (int j = 1; j < n; j++) dp[0][j] = dp[0][j - 1] + grid[0][j];
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
}
}
return dp[m - 1][n - 1];
}
滚动数组优化：
int minPathSum(vector<vector<int>>& grid) {
int m = grid.size(), n = grid[0].size();
vector<int> dp(n, INT_MAX); // INT_MAX 保证第一行取 min 时选到左方
dp[0] = 0; // 配合下面的 dp[0] += grid[0][0] 得到正确起点
for (int i = 0; i < m; i++) {
dp[0] += grid[i][0]; // 第一列只能从上方来
for (int j = 1; j < n; j++) {
dp[j] = min(dp[j], dp[j - 1]) + grid[i][j];
}
}
return dp[n - 1];
}
- 时间复杂度：O(m × n)
- 空间复杂度：O(m × n)，滚动数组优化后 O(n)
网格路径 DP 的常见坑
- 边界初始化：第一行、第一列只有一个前驱，必须单独初始化，不能直接套通用转移
- 方案数 vs 最值：「不同路径」用相加、「最小路径和」用取 min，两者写混是高频错误
- 方案数溢出：网格较大时路径数按组合数增长，必要时用
long long或按题目要求取模 - 带障碍变体（LC 63）：把障碍格的
dp值置 0（不可达）即可，注意第一行/第一列在遇到障碍后其余格子也全部不可达
9.6 背包 DP¶
背包问题是 DP 中最重要的一大类问题，也是理解 DP 思想的绝佳入口。
9.6.1 0-1 背包（模板）¶
问题：有 n 件物品和一个容量为 W 的背包。第 i 件物品的重量为 w[i]，价值为 v[i]。每件物品最多选一次，求背包能装的最大总价值。
状态定义：dp[i][j] = 考虑前 i 件物品、背包容量为 j 时的最大价值
转移方程：
\[dp[i][j] = \begin{cases} dp[i-1][j] & \text{if } j < w[i] \text{（装不下）} \\ \max(dp[i-1][j], \; dp[i-1][j-w[i]] + v[i]) & \text{otherwise} \end{cases}\]
graph TD
subgraph "第 i 件物品（重量 w[i]，价值 v[i]）"
A["dp[i][j]"] --> B{"j >= w[i] ?"}
B -->|"否（装不下）"| C["dp[i][j] = dp[i-1][j]"]
B -->|"是"| D{"选还是不选？"}
D -->|"不选"| E["dp[i-1][j]"]
D -->|"选"| F["dp[i-1][j-w[i]] + v[i]"]
E --> G["取最大值"]
F --> G
end图解转移过程（4 件物品，背包容量 5）：
| 物品 | 重量 w | 价值 v |
|---|---|---|
| 1 | 1 | 2 |
| 2 | 2 | 4 |
| 3 | 3 | 4 |
| 4 | 4 | 5 |
| i \ j | 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 2 | 2 | 2 | 2 | 2 |
| 2 | 0 | 2 | 4 | 6 | 6 | 6 |
| 3 | 0 | 2 | 4 | 6 | 6 | 8 |
| 4 | 0 | 2 | 4 | 6 | 6 | 8 |
最大价值 = 8（选物品 1 + 物品 2 + 物品 3，重量 = 1+2+3 = 6 > 5，不对） 实际最优：选物品 2 + 物品 3 = 4+4 = 8（重量 2+3 = 5 <= 5）
模板代码：
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, W;
cin >> n >> W;
vector<int> w(n + 1), v(n + 1);
for (int i = 1; i <= n; i++) cin >> w[i] >> v[i];
// dp[i][j] = 前 i 件物品、容量 j 的最大价值
vector<vector<int>> dp(n + 1, vector<int>(W + 1, 0));
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= W; j++) {
dp[i][j] = dp[i - 1][j]; // 不选第 i 件
if (j >= w[i]) {
// 选第 i 件（注意：j-w[i] >= 0 已由 if 保证）
dp[i][j] = max(dp[i][j], dp[i - 1][j - w[i]] + v[i]);
}
}
}
cout << dp[n][W] << endl;
return 0;
}
- 时间复杂度：O(n × W)
- 空间复杂度：O(n × W)
9.6.2 完全背包¶
问题：与 0-1 背包类似，但每件物品可以选无限次。
转移方程的变化：
\[dp[i][j] = \max(dp[i-1][j], \; dp[i][j-w[i]] + v[i])\]
注意第二个分支：dp[i][j-w[i]] 而不是 dp[i-1][j-w[i]]——因为第 i 件物品可以重复选。
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, W;
cin >> n >> W;
vector<int> w(n + 1), v(n + 1);
for (int i = 1; i <= n; i++) cin >> w[i] >> v[i];
vector<vector<int>> dp(n + 1, vector<int>(W + 1, 0));
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= W; j++) {
dp[i][j] = dp[i - 1][j]; // 不选第 i 件
if (j >= w[i]) {
// 选第 i 件（允许继续选第 i 件）
dp[i][j] = max(dp[i][j], dp[i][j - w[i]] + v[i]);
}
}
}
cout << dp[n][W] << endl;
return 0;
}
0-1 背包 vs 完全背包 的区别
关键区别在于转移时用的是 dp[i-1][...] 还是 dp[i][...]。
- 0-1 背包：dp[i-1][j-w[i]]（每件物品只能用一次）
- 完全背包：dp[i][j-w[i]]（同一件物品可以多次使用）
9.6.3 多重背包¶
问题：第 i 件物品最多可以选 s[i] 次。
朴素做法：在转移方程中多加一层循环，枚举选了几个第 i 件物品：
\[dp[i][j] = \max_{0 \le k \le s[i], \; k \cdot w[i] \le j} \{ dp[i-1][j - k \cdot w[i]] + k \cdot v[i] \}\]
// 朴素多重背包 O(n * W * max(s[i]))
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= W; j++) {
dp[i][j] = dp[i - 1][j];
for (int k = 1; k <= s[i] && k * w[i] <= j; k++) {
dp[i][j] = max(dp[i][j], dp[i - 1][j - k * w[i]] + k * v[i]);
}
}
}
二进制优化：将 s[i] 拆分为 1, 2, 4, 8, ..., 2^k, 余数，转化为 0-1 背包。
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, W;
cin >> n >> W;
vector<int> ws, vs; // 拆分后的重量和价值
for (int i = 0; i < n; i++) {
int w, v, s;
cin >> w >> v >> s;
// 二进制拆分
int k = 1;
while (k <= s) {
ws.push_back(k * w);
vs.push_back(k * v);
s -= k;
k *= 2;
}
if (s > 0) {
ws.push_back(s * w);
vs.push_back(s * v);
}
}
// 转化为 0-1 背包
int m = ws.size();
vector<int> dp(W + 1, 0);
for (int i = 0; i < m; i++) {
for (int j = W; j >= ws[i]; j--) { // 逆序遍历！
dp[j] = max(dp[j], dp[j - ws[i]] + vs[i]);
}
}
cout << dp[W] << endl;
return 0;
}
- 时间复杂度：O(n × W × log(max(s[i])))
9.6.4 分组背包¶
问题：有 n 组物品，每组内有若干件物品，每组最多选一件。
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, W;
cin >> n >> W;
vector<int> dp(W + 1, 0);
for (int i = 0; i < n; i++) {
int s; // 当前组的物品数
cin >> s;
vector<int> w(s), v(s);
for (int j = 0; j < s; j++) cin >> w[j] >> v[j];
// 每组最多选一件，所以逆序遍历容量
for (int j = W; j >= 0; j--) {
for (int k = 0; k < s; k++) {
if (j >= w[k]) {
dp[j] = max(dp[j], dp[j - w[k]] + v[k]);
}
}
}
}
cout << dp[W] << endl;
return 0;
}
- 时间复杂度：O(n × W × max(每组物品数))
9.6.5 背包 DP 的空间优化（滚动数组）¶
二维 DP 可以优化为一维，因为 dp[i] 只依赖于 dp[i-1]。
核心思想：用一维数组 dp[j] 代替二维数组，并逆序遍历容量。
graph TD
A["二维 dp[i][j]"] -->|"优化"| B["一维 dp[j]"]
B --> C{"物品类型"}
C -->|"0-1 背包"| D["逆序遍历 j: W → w[i]"]
C -->|"完全背包"| E["正序遍历 j: w[i] → W"]0-1 背包空间优化（必须逆序）：
// 0-1 背包一维优化
vector<int> dp(W + 1, 0);
for (int i = 1; i <= n; i++) {
for (int j = W; j >= w[i]; j--) { // 逆序！
dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
}
}
完全背包空间优化（正序即可）：
// 完全背包一维优化
vector<int> dp(W + 1, 0);
for (int i = 1; i <= n; i++) {
for (int j = w[i]; j <= W; j++) { // 正序！
dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
}
}
为什么 0-1 背包必须逆序？
如果正序遍历，dp[j - w[i]] 可能已经被当前这一轮更新过了，相当于同一件物品被选了多次——这变成了完全背包！逆序保证每件物品只被考虑一次。
空间优化总结：
| 背包类型 | 遍历顺序 | 原因 |
|---|---|---|
| 0-1 背包 | 逆序 (j: W → w[i]) | 每件物品只能用一次 |
| 完全背包 | 正序 (j: w[i] → W) | 物品可重复使用 |
| 多重背包 | 逆序（拆分后转 0-1） | 二进制拆分后按 0-1 处理 |
- 空间优化后的时间复杂度：不变
- 空间优化后的空间复杂度：O(W)
9.7 区间 DP¶
区间 DP 是一类在区间 [i, j] 上定义状态的 DP。核心思想：枚举分割点 k，将大区间拆分为 [i, k] 和 [k+1, j] 两个子区间。
一般模板：
// 区间 DP 模板
for (int len = 2; len <= n; len++) { // 枚举区间长度
for (int i = 1; i + len - 1 <= n; i++) { // 枚举左端点
int j = i + len - 1; // 右端点
for (int k = i; k < j; k++) { // 枚举分割点
dp[i][j] = min/max(dp[i][j], dp[i][k] + dp[k+1][j] + cost);
}
}
}
9.7.1 石子合并¶
问题：有 n 堆石子排成一行，每次可以合并相邻两堆，代价为两堆石子的总数。求合并所有石子的最小总代价。
状态定义：dp[i][j] = 合并第 i 到第 j 堆石子的最小代价
转移方程：
\[dp[i][j] = \min_{i \le k < j} \{ dp[i][k] + dp[k+1][j] + \sum_{t=i}^{j} a[t] \}\]
图解：
graph TD
A["合并 [i, j]"] --> B["枚举分割点 k"]
B --> C["先合并 [i, k]"]
B --> D["再合并 [k+1, j]"]
C --> E["最后合并左右两堆"]
D --> E
E --> F["代价 = dp[i][k] + dp[k+1][j] + sum(i..j)"]#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
vector<int> a(n + 1), pre(n + 1, 0);
for (int i = 1; i <= n; i++) {
cin >> a[i];
pre[i] = pre[i - 1] + a[i]; // 前缀和，方便计算区间和
}
// dp[i][j] = 合并第 i 到第 j 堆的最小代价
vector<vector<int>> dp(n + 1, vector<int>(n + 1, 0x3f3f3f3f));
for (int i = 1; i <= n; i++) dp[i][i] = 0; // 一堆不需要合并
for (int len = 2; len <= n; len++) { // 区间长度
for (int i = 1; i + len - 1 <= n; i++) { // 左端点
int j = i + len - 1; // 右端点
int sum = pre[j] - pre[i - 1]; // [i, j] 的石子总数
for (int k = i; k < j; k++) { // 枚举分割点
dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + sum);
}
}
}
cout << dp[1][n] << endl;
return 0;
}
- 时间复杂度：O(n³)
- 空间复杂度：O(n²)
9.7.2 戳气球（LC 312）¶
问题：n 个气球排成一行，每个气球上有一个数字。戳破第 i 个气球可以获得 nums[left] * nums[i] * nums[right] 个硬币，其中 left 和 right 是 i 两侧相邻的气球。求戳破所有气球能获得的最大硬币数。
正难则反：与其思考先戳哪个，不如思考最后戳哪个。
状态定义：dp[i][j] = 戳破开区间 (i, j) 内所有气球能获得的最大硬币数（不包括 i 和 j）
转移方程：
\[dp[i][j] = \max_{i < k < j} \{ dp[i][k] + dp[k][j] + nums[i] \times nums[k] \times nums[j] \}\]
#include <bits/stdc++.h>
using namespace std;
int maxCoins(vector<int>& nums) {
int n = nums.size();
// 两端加上虚拟气球（值为 1）
vector<int> val(n + 2, 1);
for (int i = 0; i < n; i++) val[i + 1] = nums[i];
// dp[i][j] = 戳破 (i, j) 之间所有气球的最大收益
vector<vector<int>> dp(n + 2, vector<int>(n + 2, 0));
// 区间长度从 1 开始（至少有 1 个气球在 i 和 j 之间）
for (int len = 1; len <= n; len++) {
for (int i = 0; i + len + 1 <= n + 1; i++) {
int j = i + len + 1;
for (int k = i + 1; k < j; k++) {
// 最后戳破气球 k
dp[i][j] = max(dp[i][j],
dp[i][k] + dp[k][j] + val[i] * val[k] * val[j]);
}
}
}
return dp[0][n + 1];
}
- 时间复杂度：O(n³)
- 空间复杂度：O(n²)
正难则反
区间 DP 中，当「正向操作」不好分析时，可以反过来思考——考虑最后一步操作，往往能简化问题。
9.8 数位 DP 简介¶
数位 DP 用于解决「统计 [L, R] 范围内满足某种条件的数字个数」的问题。
核心思想：将数字拆成每一位进行 DP，逐位枚举，通过 limit 变量控制当前位是否受限。
基本框架（以统计 [1, n] 中不含数字 4 的数的个数为例）：
#include <bits/stdc++.h>
using namespace std;
int digits[20], len; // 分解数字的每一位
long long dp[20][2]; // dp[pos][tight]
// pos: 当前处理到第几位（从高位到低位）
// tight: 当前是否受限（即前面的位都取到了上界）
// 返回：从当前位开始，合法方案数
long long dfs(int pos, bool tight, bool lead_zero) {
if (pos == len) return 1; // 所有位都填完了，找到一个合法方案
// 记忆化（只有不受限且不是前导零时才能复用）
if (!tight && !lead_zero && dp[pos][0] != -1) return dp[pos][0];
int up = tight ? digits[pos] : 9; // 当前位能填的最大值
long long res = 0;
for (int d = 0; d <= up; d++) {
if (d == 4) continue; // 跳过数字 4
res += dfs(pos + 1, tight && (d == up), lead_zero && (d == 0));
}
if (!tight && !lead_zero) dp[pos][0] = res;
return res;
}
long long solve(int n) {
len = 0;
while (n > 0) {
digits[len++] = n % 10;
n /= 10;
}
reverse(digits, digits + len); // 高位在前
memset(dp, -1, sizeof(dp));
return dfs(0, true, true);
}
int main() {
int L, R;
cin >> L >> R;
cout << solve(R) - solve(L - 1) << endl;
return 0;
}
状态参数说明：
| 参数 | 含义 |
|---|---|
pos |
当前处理的位（从高位 0 开始） |
tight |
当前是否受到上界限制 |
lead_zero |
前面是否都是前导零（用于处理「不含某数字」等限制） |
graph TD
A["dfs(pos=0, tight=true)"] --> B["枚举当前位 d = 0,1,2,3,5,6,7,8,9"]
B --> C["dfs(pos+1, tight && d==up)"]
C --> D["... 递归到 pos == len"]
D --> E["返回 1（找到一个合法数字）"]数位 DP 的常见变体
- 统计数字中某 digit 出现的次数
- 统计不含相邻相同数字的数
- 统计各位数字之和满足条件的数
- 统计能被某个数整除的数
总结¶
mindmap
root((动态规划基础))
线性 DP
爬楼梯
打家劫舍
LIS
LCS
编辑距离
最大子数组和
网格路径 DP
不同路径
最小路径和
背包 DP
0-1 背包
完全背包
多重背包
分组背包
空间优化
区间 DP
石子合并
戳气球
数位 DP
逐位枚举
tight 限制DP 学习建议
- 先理解状态含义，再记忆转移方程
- 手动模拟小样例，在草稿纸上画出 DP 表格
- 先写暴力递归，再加记忆化，最后改递推
- 背包问题是基础中的基础，务必反复练习
练习题¶
LeetCode 暑假 - 动态规划¶
| 题号 | 题目 | 难度 | 链接 | 完成 |
|---|---|---|---|---|
| 198 | House Robber | Easy | 链接 | - [ ] |
| 2094 | Finding 3-Digit Even Numbers | Easy | 链接 | - [ ] |
| 5 | Longest Palindromic Substring | Medium | 链接 | - [ ] |
| 53 | Maximum Subarray | Medium | 链接 | - [ ] |
| 213 | House Robber II | Medium | 链接 | - [ ] |
| 516 | Longest Palindromic Subsequence | Medium | 链接 | - [ ] |
| 845 | Longest Mountain in Array | Medium | 链接 | - [ ] |
| 781 | Rabbits in Forest | Medium | 链接 | - [ ] |
| 337 | House Robber III | Medium | 链接 | - [ ] |
| 174 | Dungeon Game | Hard | 链接 | - [ ] |
| 188 | Best Time to Buy and Sell Stock IV | Hard | 链接 | - [ ] |
| 233 | Number of Digit One | Hard | 链接 | - [ ] |
| 403 | Frog Jump | Hard | 链接 | - [ ] |
| 514 | Freedom Trail | Hard | 链接 | - [ ] |
扩展 6 - 记忆化搜索¶
| 题号 | 题目 | 难度 | 链接 | 完成 |
|---|---|---|---|---|
| 70 | Climbing Stairs | Easy | 链接 | - [ ] |
| 121 | Best Time to Buy and Sell Stock | Easy | 链接 | - [ ] |
| 118 | Pascal's Triangle | Easy | 链接 | - [ ] |
| 1021 | Remove Outermost Parentheses | Easy | 链接 | - [ ] |
| 122 | Best Time to Buy and Sell Stock II | Medium | 链接 | - [ ] |
| 139 | Word Break | Medium | 链接 | - [ ] |
| 397 | Integer Replacement | Medium | 链接 | - [ ] |
| 698 | Partition to K Equal Sum Subsets | Medium | 链接 | - [ ] |
| 1574 | Shortest Subarray to be Removed to Make Array Sorted | Medium | 链接 | - [ ] |
| 42 | Trapping Rain Water | Hard | 链接 | - [ ] |
| 44 | Wildcard Matching | Hard | 链接 | - [ ] |
| 72 | Edit Distance | Hard | 链接 | - [ ] |
| 913 | Cat and Mouse | Hard | 链接 | - [ ] |
| 1728 | Cat and Mouse II | Hard | 链接 | - [ ] |
寒假 DP 相关¶
以下题目在寒假学习期间推荐巩固练习：322 (Coin Change)、300 (LIS)、494 (Target Sum)、473 (Matchsticks to Square)、337 (House Robber III)、64 (Minimum Path Sum)、198 (House Robber)。
ACM Day4 - DP 基础¶
| 题号 | 平台 | 题目 | 难度 | 链接 | 完成 |
|---|---|---|---|---|---|
| 2121E | CF | Sponsor of Your Problems | 1500 | 链接 | - [ ] |
| 1969C | CF | Minimizing the Sum | 1700 | 链接 | - [ ] |
| 2069C | CF | Beautiful Sequence | 1500 | 链接 | - [ ] |
| 1984C2 | CF | Magnitude (Hard Version) | 1700 | 链接 | - [ ] |
| 1954D | CF | Colored Balls | 1800 | 链接 | - [ ] |
| 1974E | CF | Money Buys Happiness | 1800 | 链接 | - [ ] |
| 2078D | CF | Scammy Game Ad | 1800 | 链接 | - [ ] |
| dp_d | AT | Knapsack 1 | — | 链接 | - [ ] |
| dp_e | AT | Knapsack 2 | — | 链接 | - [ ] |
| dp_f | AT | LCS | — | 链接 | - [ ] |
| P9868 | 洛谷 | buying hay | — | 链接 | - [ ] |
| P2679 | 洛谷 | 子串 | — | 链接 | - [ ] |