从 0 开始学习动态规划：中学生系统掌握 DP¶
适合对象： 有 C++ 基础、正在学习算法与信息学竞赛的中学生
目标： 从“完全不知道什么是动态规划”，逐步达到能够独立分析、设计状态、写出 DP，并进一步解决较复杂的竞赛题。
动态规划（Dynamic Programming，简称 DP）是中学信息学竞赛中最重要、也最容易“感觉会了但遇到新题不会”的算法之一。
真正掌握 DP，不是背几十个模板，而是掌握下面这句话：
把一个大问题分解成许多规模更小的相同类型的问题，用状态保存已经计算过的结果，再按照状态转移关系逐步求出答案。
一、先建立动态规划的整体知识体系¶
我们先把动态规划进行分类。
动态规划 DP
│
├── 1. 线性 DP
│ ├── 最长上升子序列 LIS
│ ├── 最大子段和
│ └── 不同走法 / 爬楼梯
│
├── 2. 背包 DP
│ ├── 01 背包
│ ├── 完全背包
│ └── 多重背包
│
├── 3. 网格 DP
│ ├── 网格走法
│ ├── 最小路径和
│ └── 带障碍物路径
│
├── 4. 区间 DP
│ ├── 石子合并
│ ├── 回文串
│ └── 矩阵链乘法
│
├── 5. 树形 DP
│ ├── 树上最大独立集
│ ├── 树的最大路径
│ └── 树上背包
│
├── 6. 状态压缩 DP
│ ├── 集合状态
│ ├── 旅行商问题
│ └── 棋盘放置
│
├── 7. DAG / 拓扑 DP
│ ├── DAG 最长路
│ ├── DAG 最短路
│ └── 计数 DP
│
└── 8. 数位 DP
├── 统计数字
├── 数字和
└── 相邻数字限制
对于中学生，我建议按照：
线性 DP → 网格 DP → 背包 DP → 区间 DP → DAG DP → 树形 DP → 状态压缩 DP → 数位 DP
这个顺序学习。
二、第一关：什么是动态规划？¶
2.1 一个最简单的问题¶
假设有楼梯：
┌───┐
│ 4 │
┌───┤ │
│ 3 │ │
┌───┤ │ │
│ 2 │ │ │
│ │ │ │
└───┴───┴───┴──
1 2 3 4
每次可以走：
- 1 阶
- 2 阶
问：
走到第 n 阶有多少种不同的方法？
例如：
n = 1¶
只有：
1
所以：
f[1] = 1
n = 2¶
两种：
1 + 1
2
所以：
f[2] = 2
n = 3¶
最后一步有两种可能：
从第 2 阶走 1 步
从第 1 阶走 2 步
所以：
f[3] = f[2] + f[1]
于是：
f[3] = 2 + 1 = 3
继续：
f[4] = f[3] + f[2]
即：
f[4] = 3 + 2 = 5
三、动态规划最重要的 5 个问题¶
以后遇到 DP 题，不要马上写代码。
先问自己：
问题 1：状态是什么？¶
例如：
dp[i]
可能表示：
到达第 i 个位置时的最优答案。
问题 2：最后一步是什么？¶
这是 DP 中非常重要的思维。
例如爬楼梯：
到达第 i 阶：
第 i 阶
↑
/ \
i-1 i-2
因此：
dp[i] = dp[i-1] + dp[i-2]
问题 3：状态如何转移？¶
也就是：
当前状态由哪些以前的状态得到？
例如：
dp[i] = dp[i - 1] + dp[i - 2];
问题 4：初始状态是什么？¶
例如：
dp[1] = 1;
dp[2] = 2;
问题 5：最终答案在哪里？¶
例如：
cout << dp[n];
四、动态规划的核心公式¶
可以把 DP 总结成：
状态
↓
状态转移
↓
初始状态
↓
计算顺序
↓
最终答案
也就是：
dp[当前] = 根据若干 dp[之前] 计算
第一类：线性 DP¶
线性 DP 是最适合入门的 DP。
典型特征：
状态通常按照
1 → 2 → 3 → ... → n的顺序计算。
题目 1：爬楼梯¶
题目¶
有 n 阶楼梯，每次可以爬：
- 1 阶
- 2 阶
问到达第 n 阶有多少种不同方法。
1. 状态设计¶
定义：
dp[i]
表示：
到达第
i阶的方法数量。
2. 状态转移¶
到达第 i 阶，最后一步只有两种情况：
i-1 → i
i-2 → i
所以：
dp[i] = dp[i-1] + dp[i-2]
3. 初始值¶
dp[1] = 1
dp[2] = 2
4. C++ 完整代码¶
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
vector<long long> dp(n + 1);
if (n >= 1)
dp[1] = 1;
if (n >= 2)
dp[2] = 2;
for (int i = 3; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
cout << dp[n] << endl;
return 0;
}
题目 2：最大子段和¶
题目¶
给定：
-2 1 -3 4 -1 2 1 -5 4
找出一个连续子数组，使它的和最大。
答案：
4 + (-1) + 2 + 1 = 6
所以答案是：
6
1. 状态设计¶
定义：
dp[i]
表示：
必须以第 i 个元素结尾的最大连续子段和。
这是一个非常重要的 DP 技巧：
状态定义必须足够精确。
2. 考虑第 i 个元素¶
假设当前：
a[i]
有两种选择。
情况一¶
自己重新开始：
a[i]
情况二¶
接在前面的最大子段后面：
dp[i-1] + a[i]
因此：
dp[i] = max(a[i], dp[i-1] + a[i])
3. C++ 完整代码¶
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
vector<long long> a(n + 1);
vector<long long> dp(n + 1);
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
dp[1] = a[1];
long long answer = dp[1];
for (int i = 2; i <= n; i++) {
dp[i] = max(a[i], dp[i - 1] + a[i]);
answer = max(answer, dp[i]);
}
cout << answer << endl;
return 0;
}
题目 3：最长上升子序列 LIS¶
题目¶
给出：
1 5 2 4 3 7
求最长严格上升子序列长度。
例如：
1 2 3 7
长度为：
4
注意：
子序列不要求连续。
1. 状态设计¶
定义：
dp[i]
表示：
以
a[i]结尾的最长上升子序列长度。
2. 状态转移¶
如果：
a[j] < a[i]
那么：
dp[i] = max(dp[i], dp[j] + 1)
其中：
j < i
3. C++ 完整代码¶
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
vector<int> a(n + 1);
vector<int> dp(n + 1, 1);
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
int answer = 1;
for (int i = 1; i <= n; i++) {
for (int j = 1; j < i; j++) {
if (a[j] < a[i]) {
dp[i] = max(dp[i], dp[j] + 1);
}
}
answer = max(answer, dp[i]);
}
cout << answer << endl;
return 0;
}
复杂度：
时间：O(n²)
空间：O(n)
第二类：网格 DP¶
网格 DP 是中学生非常容易理解的一类 DP。
例如：
┌───┬───┬───┬───┐
│ │ │ │ │
├───┼───┼───┼───┤
│ │ │ │ │
├───┼───┼───┼───┤
│ │ │ │ │
└───┴───┴───┴───┘
典型特征：
状态通常是
dp[i][j]。
题目 1：网格走法¶
只能：
向右 →
向下 ↓
问从左上角走到右下角有多少种方法。
状态¶
dp[i][j]
表示：
从
(1,1)走到(i,j)的方案数。
到达 (i,j)：
左边 → 当前
上边 ↓ 当前
所以：
dp[i][j] = dp[i-1][j] + dp[i][j-1]
C++ 完整代码¶
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, m;
cin >> n >> m;
vector<vector<long long>> dp(
n + 1,
vector<long long>(m + 1, 0)
);
dp[1][1] = 1;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (i == 1 && j == 1)
continue;
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}
}
cout << dp[n][m] << endl;
return 0;
}
题目 2：最小路径和¶
每个格子有一个数字，只能向右或向下。
求从左上角到右下角的最小数字和。
例如：
1 3 1
1 5 1
4 2 1
最佳路线：
1 → 3 → 1 → 1 → 1
答案：
7
状态¶
dp[i][j]
表示：
到达
(i,j)的最小路径和。
转移：
dp[i][j]
=
min(dp[i-1][j], dp[i][j-1])
+ a[i][j]
C++ 完整代码¶
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, m;
cin >> n >> m;
vector<vector<long long>> a(
n + 1,
vector<long long>(m + 1)
);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cin >> a[i][j];
}
}
const long long INF = 4e18;
vector<vector<long long>> dp(
n + 1,
vector<long long>(m + 1, INF)
);
dp[1][1] = a[1][1];
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (i == 1 && j == 1)
continue;
dp[i][j] = min(
dp[i - 1][j],
dp[i][j - 1]
) + a[i][j];
}
}
cout << dp[n][m] << endl;
return 0;
}
题目 3：带障碍物的网格¶
有些格子不能走。
例如：
S . .
. # .
. . T
其中：
S：起点
T：终点
#：障碍
求方案数。
状态¶
仍然是：
dp[i][j]
但是：
如果是障碍：
dp[i][j] = 0
否则：
dp[i][j]
=
dp[i-1][j]
+
dp[i][j-1]
C++ 完整代码¶
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, m;
cin >> n >> m;
vector<string> grid(n + 1);
for (int i = 1; i <= n; i++) {
string s;
cin >> s;
grid[i] = " " + s;
}
vector<vector<long long>> dp(
n + 1,
vector<long long>(m + 1, 0)
);
dp[1][1] = 1;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (grid[i][j] == '#') {
dp[i][j] = 0;
continue;
}
if (i == 1 && j == 1)
continue;
dp[i][j] =
dp[i - 1][j] +
dp[i][j - 1];
}
}
cout << dp[n][m] << endl;
return 0;
}
第三类：背包 DP¶
背包 DP 是信息学竞赛中最重要的 DP 类型之一。
核心思想：
有限资源 + 选择物品 + 求最优值/方案数。
题目 1：01 背包¶
有 n 个物品。
每个物品：
重量 w[i]
价值 v[i]
背包容量为：
W
每个物品：
最多只能选择一次。
求最大价值。
状态¶
dp[j]
表示：
容量不超过
j时能够获得的最大价值。
转移¶
对于物品 i：
不选¶
dp[j]
选择¶
dp[j-w[i]] + v[i]
所以：
dp[j]
=
max(dp[j], dp[j-w[i]] + v[i])
最关键的问题：为什么 j 要倒序？¶
for (int j = W; j >= w[i]; j--)
因为如果正序：
j = w[i] → W
当前物品可能被重复使用。
倒序可以保证：
当前物品只使用一次。
这是 01 背包最重要的代码特征。
C++ 完整代码¶
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, W;
cin >> n >> W;
vector<int> w(n + 1);
vector<int> v(n + 1);
for (int i = 1; i <= n; i++) {
cin >> w[i] >> v[i];
}
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]
);
}
}
cout << dp[W] << endl;
return 0;
}
题目 2：完全背包¶
与 01 背包不同：
每个物品可以无限次选择。
例如：
物品：
重量 价值
2 3
3 4
4 5
容量：
7
状态转移¶
仍然：
dp[j]
=
max(dp[j], dp[j-w[i]] + v[i])
但是循环方向改变：
for (int j = w[i]; j <= W; j++)
也就是：
完全背包正序。
C++ 完整代码¶
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, W;
cin >> n >> W;
vector<int> w(n + 1);
vector<int> v(n + 1);
for (int i = 1; i <= n; i++) {
cin >> 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]
);
}
}
cout << dp[W] << endl;
return 0;
}
题目 3：多重背包¶
每种物品有数量限制：
重量 w
价值 v
最多有 c 件
例如：
物品1：重量2，价值3，最多4件
物品2：重量3，价值5，最多2件
最直观的方法¶
枚举当前物品选择：
0 件
1 件
2 件
...
c 件
状态：
dp[j]
转移¶
dp[j]
=
max(
dp[j],
dp[j-k*w] + k*v
)
其中：
0 <= k <= c
C++ 完整代码¶
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, W;
cin >> n >> W;
vector<int> w(n + 1);
vector<int> v(n + 1);
vector<int> c(n + 1);
for (int i = 1; i <= n; i++) {
cin >> w[i] >> v[i] >> c[i];
}
vector<int> dp(W + 1, 0);
for (int i = 1; i <= n; i++) {
for (int j = W; j >= 0; j--) {
for (int k = 1;
k <= c[i] && k * w[i] <= j;
k++) {
dp[j] = max(
dp[j],
dp[j - k * w[i]] + k * v[i]
);
}
}
}
cout << dp[W] << endl;
return 0;
}
三种背包必须记住¶
| 类型 | 每件物品使用次数 | j 的方向 |
|---|---|---|
| 01 背包 | 1 次 | 从大到小 |
| 完全背包 | 无限 | 从小到大 |
| 多重背包 | 有限制 | 通常需要额外处理 |
最重要的口诀：
01 背包倒序，完全背包正序。
第四类：区间 DP¶
区间 DP 是难度明显上升的一类。
核心特点：
状态表示一个区间
[l,r]。
因此状态通常：
dp[l][r]
题目 1：石子合并¶
有一排石子：
a1 a2 a3 ... an
每次只能合并相邻的两堆。
合并费用：
两堆石子的总数量
求把所有石子合成一堆的最小费用。
为什么是区间 DP？¶
因为最后一定是：
[l, r]
整个区间合并成一堆。
假设最后一次合并的位置是：
k
那么：
[l,k]
和：
[k+1,r]
分别已经合并好了。
因此：
dp[l][r]
=
min(
dp[l][k]
+
dp[k+1][r]
+
sum(l,r)
)
C++ 完整代码¶
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
vector<long long> a(n + 1);
vector<long long> prefix(n + 1, 0);
for (int i = 1; i <= n; i++) {
cin >> a[i];
prefix[i] = prefix[i - 1] + a[i];
}
auto sum = [&](int l, int r) {
return prefix[r] - prefix[l - 1];
};
const long long INF = 4e18;
vector<vector<long long>> dp(
n + 1,
vector<long long>(n + 1, 0)
);
for (int len = 2; len <= n; len++) {
for (int l = 1; l + len - 1 <= n; l++) {
int r = l + len - 1;
dp[l][r] = INF;
for (int k = l; k < r; k++) {
dp[l][r] = min(
dp[l][r],
dp[l][k]
+ dp[k + 1][r]
+ sum(l, r)
);
}
}
}
cout << dp[1][n] << endl;
return 0;
}
题目 2：最长回文子序列¶
例如：
bbbab
最长回文子序列：
bbbb
答案：
4
状态¶
dp[l][r]
表示：
字符串
[l,r]的最长回文子序列长度。
情况 1¶
如果：
s[l] == s[r]
那么：
dp[l][r]
=
dp[l+1][r-1] + 2
情况 2¶
如果：
s[l] != s[r]
那么至少舍弃一个端点：
dp[l][r]
=
max(
dp[l+1][r],
dp[l][r-1]
)
C++ 完整代码¶
#include <bits/stdc++.h>
using namespace std;
int main() {
string s;
cin >> s;
int n = s.size();
vector<vector<int>> dp(
n,
vector<int>(n, 0)
);
for (int i = 0; i < n; i++) {
dp[i][i] = 1;
}
for (int len = 2; len <= n; len++) {
for (int l = 0; l + len - 1 < n; l++) {
int r = l + len - 1;
if (s[l] == s[r]) {
if (len == 2)
dp[l][r] = 2;
else
dp[l][r] = dp[l + 1][r - 1] + 2;
} else {
dp[l][r] = max(
dp[l + 1][r],
dp[l][r - 1]
);
}
}
}
cout << dp[0][n - 1] << endl;
return 0;
}
题目 3：矩阵链乘法¶
给出：
A1 × A2 × A3 × ... × An
矩阵乘法满足结合律：
(A1 × A2) × A3
和：
A1 × (A2 × A3)
结果相同。
但是计算次数可能不同。
求最少的乘法次数。
状态¶
dp[l][r]
表示：
计算矩阵
l到r的最小乘法次数。
最后一次分割：
l ... k | k+1 ... r
所以：
dp[l][r]
=
min(
dp[l][k]
+
dp[k+1][r]
+
cost
)
C++ 完整代码¶
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
vector<long long> p(n + 1);
for (int i = 0; i <= n; i++) {
cin >> p[i];
}
const long long INF = 4e18;
vector<vector<long long>> dp(
n + 1,
vector<long long>(n + 1, 0)
);
for (int len = 2; len <= n; len++) {
for (int l = 1; l + len - 1 <= n; l++) {
int r = l + len - 1;
dp[l][r] = INF;
for (int k = l; k < r; k++) {
long long cost =
dp[l][k]
+ dp[k + 1][r]
+ p[l - 1] * p[k] * p[r];
dp[l][r] = min(
dp[l][r],
cost
);
}
}
}
cout << dp[1][n] << endl;
return 0;
}
第五类：DAG / 拓扑 DP¶
DAG：
Directed Acyclic Graph
有向无环图。
如果一个问题可以表示成：
状态 A → 状态 B
并且不存在环，就可以考虑 DP。
题目 1：DAG 最长路径¶
给定一个 DAG。
求从 1 出发能够达到的最长路径。
状态¶
dp[v]
表示：
到达节点
v的最长路径长度。
对于边：
u → v
有：
dp[v] = max(dp[v], dp[u] + w)
C++ 完整代码¶
#include <bits/stdc++.h>
using namespace std;
struct Edge {
int to;
int weight;
};
int main() {
int n, m;
cin >> n >> m;
vector<vector<Edge>> graph(n + 1);
vector<int> indegree(n + 1, 0);
for (int i = 0; i < m; i++) {
int u, v, w;
cin >> u >> v >> w;
graph[u].push_back({v, w});
indegree[v]++;
}
queue<int> q;
for (int i = 1; i <= n; i++) {
if (indegree[i] == 0)
q.push(i);
}
vector<int> dp(n + 1, 0);
while (!q.empty()) {
int u = q.front();
q.pop();
for (auto e : graph[u]) {
int v = e.to;
dp[v] = max(
dp[v],
dp[u] + e.weight
);
indegree[v]--;
if (indegree[v] == 0)
q.push(v);
}
}
int answer = 0;
for (int i = 1; i <= n; i++) {
answer = max(answer, dp[i]);
}
cout << answer << endl;
return 0;
}
题目 2：DAG 路径计数¶
从节点 1 到节点 n 有多少条路径？
状态：
dp[v]
表示：
从
1到v的路径数量。
对于：
u → v
有：
dp[v] += dp[u]
C++ 完整代码¶
#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1000000007;
int main() {
int n, m;
cin >> n >> m;
vector<vector<int>> graph(n + 1);
vector<int> indegree(n + 1, 0);
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
graph[u].push_back(v);
indegree[v]++;
}
queue<int> q;
for (int i = 1; i <= n; i++) {
if (indegree[i] == 0)
q.push(i);
}
vector<long long> dp(n + 1, 0);
dp[1] = 1;
while (!q.empty()) {
int u = q.front();
q.pop();
for (int v : graph[u]) {
dp[v] += dp[u];
dp[v] %= MOD;
indegree[v]--;
if (indegree[v] == 0)
q.push(v);
}
}
cout << dp[n] << endl;
return 0;
}
题目 3：DAG 最短路¶
状态：
dp[v]
表示：
从起点到
v的最短距离。
对于边：
u → v
：
dp[v]
=
min(dp[v], dp[u] + w)
这与 DAG 最长路的区别只有：
max
变成：
min
第六类：树形 DP¶
树形 DP 是信息学竞赛中非常重要的一类。
假设：
1
/ \
2 3
/ \
4 5
每个节点都有自己的状态。
题目 1：树上最大独立集¶
要求：
选择尽可能多的节点，但是父子节点不能同时选择。
例如：
1
/ \
2 3
/ \
4 5
可以选择：
1 4 5
也可以：
2 3
状态¶
定义：
dp[u][0]
dp[u][1]
含义：
dp[u][0]：
不选择 u 时，子树最大答案
dp[u][1]：
选择 u 时，子树最大答案
转移¶
如果选择 u：
dp[u][1]
=
1
+
所有 dp[v][0]
因为：
选择父节点 u，就不能选择孩子 v。
如果不选择 u：
dp[u][0]
=
sum(max(dp[v][0], dp[v][1]))
C++ 完整代码¶
#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> graph;
vector<vector<int>> dp;
void dfs(int u, int parent) {
dp[u][0] = 0;
dp[u][1] = 1;
for (int v : graph[u]) {
if (v == parent)
continue;
dfs(v, u);
dp[u][0] += max(
dp[v][0],
dp[v][1]
);
dp[u][1] += dp[v][0];
}
}
int main() {
int n;
cin >> n;
graph.resize(n + 1);
dp.resize(n + 1, vector<int>(2));
for (int i = 1; i < n; i++) {
int u, v;
cin >> u >> v;
graph[u].push_back(v);
graph[v].push_back(u);
}
dfs(1, 0);
cout << max(
dp[1][0],
dp[1][1]
) << endl;
return 0;
}
题目 2：树的最大路径和¶
每个节点有一个权值：
5
/ \
2 8
/ \
3 4
求树中任意两个节点之间路径上的最大权值和。
核心思想¶
对于节点 u：
记录：
从
u向下面走能够得到的最大路径。
然后考虑：
左边最长 + u + 右边最长
C++ 完整代码¶
#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> graph;
vector<long long> value;
long long answer = LLONG_MIN;
long long dfs(int u, int parent) {
long long best1 = 0;
long long best2 = 0;
for (int v : graph[u]) {
if (v == parent)
continue;
long long child = dfs(v, u);
if (child > best1) {
best2 = best1;
best1 = child;
}
else if (child > best2) {
best2 = child;
}
}
answer = max(
answer,
value[u] + best1 + best2
);
return value[u] + best1;
}
int main() {
int n;
cin >> n;
value.resize(n + 1);
graph.resize(n + 1);
for (int i = 1; i <= n; i++) {
cin >> value[i];
}
for (int i = 1; i < n; i++) {
int u, v;
cin >> u >> v;
graph[u].push_back(v);
graph[v].push_back(u);
}
dfs(1, 0);
cout << answer << endl;
return 0;
}
题目 3：树上选择问题¶
要求：
选择一些节点，父子节点不能同时选择，并且每个节点具有价值，求最大价值。
这实际上就是题目 1 的加权版本。
状态仍然：
dp[u][0]
dp[u][1]
但是：
dp[u][1] = value[u]
然后：
dp[u][1] += dp[v][0]
第七类：状态压缩 DP¶
这是从中级进入高级的重要一步。
核心思想：
用一个整数的二进制位表示一个集合。
例如：
5 = 0101
可以表示：
第 0 个元素选了
第 2 个元素选了
题目 1：旅行商问题 TSP¶
有 n 个城市。
从城市 0 出发：
每个城市访问恰好一次，最后回到
0。
求最小费用。
状态¶
dp[mask][i]
表示：
已经访问了
mask中的城市，并且当前位于城市i时的最小费用。
例如：
mask = 01011
表示访问：
0、1、3
转移¶
从：
i
前往：
j
：
newMask = mask | (1 << j)
然后：
dp[newMask][j]
=
min(
dp[newMask][j],
dp[mask][i] + cost[i][j]
)
C++ 完整代码¶
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
vector<vector<int>> cost(
n,
vector<int>(n)
);
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cin >> cost[i][j];
}
}
const long long INF = 4e18;
int total = 1 << n;
vector<vector<long long>> dp(
total,
vector<long long>(n, INF)
);
dp[1][0] = 0;
for (int mask = 0; mask < total; mask++) {
for (int u = 0; u < n; u++) {
if (dp[mask][u] == INF)
continue;
if (!(mask & (1 << u)))
continue;
for (int v = 0; v < n; v++) {
if (mask & (1 << v))
continue;
int newMask =
mask | (1 << v);
dp[newMask][v] = min(
dp[newMask][v],
dp[mask][u] + cost[u][v]
);
}
}
}
long long answer = INF;
int full = (1 << n) - 1;
for (int i = 1; i < n; i++) {
answer = min(
answer,
dp[full][i] + cost[i][0]
);
}
cout << answer << endl;
return 0;
}
复杂度：
O(2^n × n²)
因此通常：
n ≤ 20
左右才比较适合。
题目 2：集合选取¶
有 n 个元素，每个元素有价值。
要求选择一个集合，使：
某些元素之间不能同时出现。
这类题目经常可以转化为：
mask
表示当前已经选择了哪些元素。
题目 3：棋盘状态压缩 DP¶
例如：
在一个
n × m棋盘上放置棋子，要求任意两个棋子不能相邻。
可以使用：
mask
表示一行中哪些位置放了棋子。
例如：
01010
表示：
第 2、4 个位置放棋子
然后：
dp[i][mask]
表示：
前 i 行，第 i 行状态为 mask 时的最大方案数。
这是状态压缩 DP 在棋盘问题中的典型形式。
第八类：数位 DP¶
数位 DP 是中学生 DP 中相对高级的一类。
典型问题：
统计
1 ~ N中满足某种数字条件的整数数量。
例如：
1 ~ N中有多少个数字不包含数字7？
为什么普通枚举不行？¶
如果：
N = 10^18
显然不能：
for (long long i = 1; i <= N; i++)
所以需要：
按数字位进行 DP。
数位 DP 的典型状态¶
常见状态：
dp[pos][state][limit]
其中：
pos
表示处理到第几位。
state
表示当前已经记录的信息。
limit
表示：
当前前缀是否受到 N 的限制。
题目 1：统计不含 7 的数字¶
例如：
N = 100
统计：
1 ~ 100
中不包含数字 7 的数字。
C++ 完整代码¶
#include <bits/stdc++.h>
using namespace std;
string s;
long long memo[20][2];
bool vis[20][2];
long long dfs(
int pos,
bool tight
) {
if (pos == (int)s.size()) {
return 1;
}
if (!tight && vis[pos][0]) {
return memo[pos][0];
}
long long ans = 0;
int limit = tight
? s[pos] - '0'
: 9;
for (int digit = 0; digit <= limit; digit++) {
if (digit == 7)
continue;
bool nextTight =
tight && (digit == limit);
ans += dfs(
pos + 1,
nextTight
);
}
if (!tight) {
vis[pos][0] = true;
memo[pos][0] = ans;
}
return ans;
}
int main() {
cin >> s;
cout << dfs(0, true) << endl;
return 0;
}
这里需要特别注意：
leading zero
前导零的处理。
在更复杂的数位 DP 中通常还需要：
started
表示：
真正的数字是否已经开始。
题目 2：统计数字和¶
求：
1 ~ N
中所有数字的数位和。
例如：
1 + 2 + ... + 9 + 10 + 11 + ...
这类题目可以使用：
pos
sum
tight
进行状态设计。
题目 3：不出现连续相同数字¶
例如统计：
1 ~ N
中满足：
不存在连续两个相同数字
的数字数量。
状态可以设计成：
dp[pos][last][tight]
其中：
pos
当前位。
last
上一位数字。
tight
是否受到 N 限制。
转移时：
if digit == last
不允许
这就是数位 DP 的典型思想。
九、动态规划中最重要的“状态设计”¶
学习 DP，真正的难点不是代码。
而是：
如何定义 dp。
下面给出一个非常重要的“状态设计表”。
| 问题类型 | 常见状态 |
|---|---|
| 爬楼梯 | dp[i] |
| 最大子段和 | dp[i] |
| LIS | dp[i] |
| 网格 | dp[i][j] |
| 01 背包 | dp[j] |
| 区间 DP | dp[l][r] |
| 树形 DP | dp[u][state] |
| DAG DP | dp[u] |
| 状态压缩 | dp[mask][state] |
| 数位 DP | dp[pos][state][limit] |
十、遇到一道新 DP 题，按照这个流程思考¶
以后给学生做题，我建议强制执行下面的流程。
Step 1：判断是不是 DP¶
问：
一个大问题能不能拆成很多相同类型的小问题？
如果可以，继续。
Step 2：定义状态¶
问：
dp[...]到底表示什么？
必须用一句完整中文说出来。
例如：
dp[i]表示以第 i 个元素结尾的最长上升子序列长度。
而不是：
dp 是答案。
这是非常重要的区别。
Step 3：寻找最后一步¶
这是最强的 DP 思维之一。
例如：
dp[i]
问：
到达 i 之前最后在哪里？
例如爬楼梯：
i-1 → i
i-2 → i
LIS：
j → i
区间 DP：
[l,k] + [k+1,r]
树形 DP：
父节点 ← 子节点
Step 4：写转移方程¶
例如：
dp[i] = dp[i-1] + dp[i-2]
或者：
dp[i] = max(dp[i], dp[j] + 1)
或者：
dp[l][r]
=
min(
dp[l][k]
+ dp[k+1][r]
+ cost
)
Step 5：确定初始化¶
例如：
dp[1] = 1;
或者：
dp[i][i] = 1;
初始化错误是 DP 最常见的错误之一。
Step 6：确定计算顺序¶
这是非常重要的一步。
例如：
线性 DP¶
i = 1 → n
网格 DP¶
左上 → 右下
区间 DP¶
区间长度从小到大
DAG DP¶
拓扑序
树形 DP¶
后序 DFS
数位 DP¶
从高位到低位
十一、DP 的三个核心组成部分¶
可以把任何 DP 题强行写成：
状态
↓
dp[i] 是什么？
↓
状态转移
↓
dp 如何从以前状态得到？
↓
初始状态
↓
从哪里开始？
↓
计算顺序
↓
最终答案
十二、最容易犯的 10 个错误¶
错误 1：不知道 dp 表示什么¶
错误：
dp[i] = ...
却不知道 dp[i] 的具体含义。
错误 2：状态定义不完整¶
例如 LIS：
错误：
dp[i] = 前 i 个元素的答案
更好的定义：
dp[i] = 以 a[i] 结尾的最长上升子序列长度
错误 3：初始化错误¶
例如：
vector<int> dp(n);
默认全是：
0
但有些 DP 的初始值必须是：
1
或者：
-INF
或者：
INF
错误 4：01 背包循环方向错误¶
错误：
for (int j = w[i]; j <= W; j++)
这会让物品重复使用。
01 背包：
for (int j = W; j >= w[i]; j--)
错误 5：区间 DP 顺序错误¶
不能随便：
for (l)
for (r)
通常需要：
for (len = 1; len <= n; len++)
保证：
dp[l][k]
dp[k+1][r]
已经计算。
错误 6：忘记考虑“最后一步”¶
这是最常见的思维障碍。
遇到 DP：
先想最后一步。
错误 7：把 DP 当成暴力搜索¶
暴力：
枚举所有可能
DP：
相同子问题只计算一次
错误 8：DP 数组开太大¶
例如：
int dp[100000][100000];
直接爆内存。
需要考虑：
状态压缩
滚动数组
一维 DP
错误 9：没有考虑数据范围¶
如果：
n = 100000
通常：
O(n²)
可能不行。
如果：
n = 20
那么：
O(2^n n²)
反而可能可以。
所以：
先看数据范围，再决定算法。
错误 10：背模板¶
这是最危险的。
不要记：
LIS = 这个模板
背包 = 那个模板
而应该记：
为什么这样定义状态？
为什么这样转移？
为什么循环顺序是这样？
十三、中学生 DP 学习路线¶
建议分成 5 个阶段。
第一阶段：DP 入门¶
目标：
能看懂简单 DP。
学习：
1. 什么是状态
2. 什么是状态转移
3. 初始化
4. 计算顺序
练习：
爬楼梯
斐波那契
走方格
最大子段和
第二阶段：线性 DP + 网格 DP¶
学习：
dp[i]
dp[i][j]
重点题型：
LIS
最长公共子序列 LCS
最大子段和
网格路径
最小路径
重点掌握：
“最后一步”分析法。
第三阶段：背包 DP¶
这是非常重要的阶段。
必须掌握：
01 背包
完全背包
多重背包
分组背包
二维费用背包
背包求方案数
背包求具体方案
重点理解：
为什么 01 背包倒序？
为什么完全背包正序？
第四阶段：高级 DP¶
学习：
区间 DP
树形 DP
DAG DP
状态压缩 DP
数位 DP
这个阶段开始真正进入竞赛级 DP。
第五阶段：综合 DP¶
最后学习：
DP + 二分
DP + 贪心
DP + 图论
DP + 数据结构
DP + 单调队列
DP + 线段树
DP 优化
例如：
斜率优化 DP
四边形不等式优化
单调队列优化
分治优化
树上背包
十四、DP 难度阶梯¶
可以把 DP 学习分成下面几个等级：
Level 0
│
├── 斐波那契
├── 爬楼梯
└── 简单网格
↓
Level 1
│
├── 最大子段和
├── LIS
└── LCS
↓
Level 2
│
├── 01 背包
├── 完全背包
└── 多重背包
↓
Level 3
│
├── 区间 DP
├── DAG DP
└── 树形 DP
↓
Level 4
│
├── 状态压缩 DP
├── 数位 DP
└── 树上背包
↓
Level 5
│
├── DP 优化
├── 单调队列优化
├── 斜率优化
└── 综合 DP
十五、学生必须掌握的 DP 模板¶
模板 1：一维 DP¶
vector<long long> dp(n + 1);
for (int i = 1; i <= n; i++) {
// 根据以前的状态计算 dp[i]
}
模板 2：二维 DP¶
vector<vector<long long>> dp(
n + 1,
vector<long long>(m + 1)
);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
// 状态转移
}
}
模板 3：01 背包¶
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]
);
}
}
模板 4：完全背包¶
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]
);
}
}
模板 5：区间 DP¶
for (int len = 2; len <= n; len++) {
for (int l = 1; l + len - 1 <= n; l++) {
int r = l + len - 1;
for (int k = l; k < r; k++) {
dp[l][r] = min(
dp[l][r],
dp[l][k]
+ dp[k + 1][r]
+ cost
);
}
}
}
模板 6：树形 DP¶
void dfs(int u, int parent) {
for (int v : graph[u]) {
if (v == parent)
continue;
dfs(v, u);
// dp[u] 根据 dp[v] 转移
}
}
模板 7：状态压缩 DP¶
for (int mask = 0; mask < (1 << n); mask++) {
for (int i = 0; i < n; i++) {
if (mask & (1 << i)) {
// 状态转移
}
}
}
十六、真正掌握 DP 的标准¶
学生学完之后，不应该只是能够写：
dp[i] = ...
而应该能够面对一道陌生题，按照下面的顺序说出来：
① 我认为这是一个 DP 问题。
② 我定义
dp[...]表示……③ 考虑最后一步，当前状态可以由……转移过来。
④ 所以状态转移方程是……
⑤ 初始状态是……
⑥ 根据依赖关系，计算顺序应该是……
⑦ 状态数量是……
⑧ 每个状态转移需要……时间。
⑨ 因此总时间复杂度是……。
⑩ 最终答案是
dp[...]。
如果一个中学生能够完整说出这十步，才可以认为他真正开始掌握动态规划。
十七、建议的系统课程安排¶
如果把动态规划真正教成一门课程，我建议安排 12 个阶段：
| 阶段 | 内容 | 目标 |
|---|---|---|
| 01 | DP 基本思想 | 理解什么是 DP |
| 02 | 一维线性 DP | 掌握 dp[i] |
| 03 | 二维/网格 DP | 掌握 dp[i][j] |
| 04 | LIS/LCS | 掌握序列 DP |
| 05 | 01 背包 | 掌握选择模型 |
| 06 | 完全/多重背包 | 掌握背包变形 |
| 07 | 区间 DP | 掌握 dp[l][r] |
| 08 | DAG DP | 掌握图上的 DP |
| 09 | 树形 DP | 掌握 DFS + DP |
| 10 | 状态压缩 DP | 掌握集合状态 |
| 11 | 数位 DP | 掌握数字限制 |
| 12 | DP 优化 | 进入竞赛提高阶段 |
十八、最重要的一张思维导图¶
最后把整个动态规划体系压缩成一张图：
动态规划
│
┌─────────────┴─────────────┐
│ │
状态设计 状态转移
│ │
┌──────┼──────┐ ┌──────┼──────┐
│ │ │ │ │ │
一维 二维 集合 加法 最大值 最小值
│ │ │
dp[i] dp[i][j] dp[mask]
│ │ │
├──────┼──────┼──────────────────┐
│ │ │ │
线性 网格 背包 状态压缩
│ │ │ │
│ │ 01/完全/多重 │
│ │ │
└──────┴──────────┬──────────────┘
│
更高级的结构
│
┌────────────┼────────────┐
│ │ │
区间 DP 树形 DP DAG DP
│ │ │
└────────────┼────────────┘
│
高级 DP
│
┌────────┴────────┐
│ │
数位 DP DP 优化
│
┌─────────────┼─────────────┐
│ │ │
单调队列 斜率优化 分治优化
十九、给中学生的最终口诀¶
学习 DP 时，可以让学生背下面这段口诀：
先判断，后定义；
找状态，想含义；
看最后，找转移；
定初值，排顺序；
算复杂，查边界；
写代码，再验证。
而面对一道真正的 DP 题，最应该反复问自己的只有三个问题：
① dp 到底表示什么？
② 当前状态从哪里来？
③ 为什么所有情况都被考虑到了？
只要这三个问题能够回答清楚，代码实际上只是把数学关系翻译成 C++。
如果按照中学生信息学奥赛的标准继续深入，下一步最值得系统学习的是 “线性 DP → LIS/LCS → 01 背包 → 完全背包 → 多重背包 → 区间 DP”，并通过由易到难的题目训练“状态定义”和“状态转移”能力，而不是继续单纯增加模板数量。