DP入门—状态与转移

前言

上一章 图论 里我们处理了最短路、连通性、匹配这些”图上的问题”。但有一类问题它们不太一样——需要做一系列决策，每个决策影响后续的选择。比如：

• 青蛙站在台阶 1，每次跳 1 或 2 步，怎么跳到台阶 $N$ 花费最少？
• 从网格左上角走到右下角，只能往右或往下，有多少种走法？
• 字符串 “atcoder” 作为子序列出现了多少次？

这些问题有一个共同特征：大问题的答案可以从小问题的答案推导出来。这不就是递推吗？没错，DP（动态规划）本质上就是”带备忘录的递推”——先算小问题，存起来，用小问题的答案算大问题。

这篇文章会用三个经典模型建立 DP 的思维框架：一维最优化、二维计数、匹配计数。

问题的本质

从暴力到 DP：一个关键观察

假设你站在台阶 5，之前从台阶 1 跳过来。你只关心一件事：到达台阶 5 的最小花费是多少？ 你不关心中间具体经过了哪些台阶——这就是”无后效性”。

暴力枚举所有跳法：每步 1 或 2 格，组合数是斐波那契级别，$O(2^N)$。

DP 的思路完全不同：只存”到达第 $i$ 个台阶的最小花费”，用第 $i-1$ 和第 $i-2$ 个的结果推出来。 这样只需要 $O(N)$ 时间。

这就是 DP 的三步法：

1. 定义状态：$dp[i]$ 表示什么？
2. 写转移方程：$dp[i]$ 从哪些状态转移过来？
3. 确定初始值和计算顺序

状态设计的核心原则

无后效性：当前状态一旦确定，未来的决策不需要知道”你是怎么到达当前状态的”。青蛙跳台阶满足无后效性——到达台阶 5 的最小花费只取决于台阶 3 和 4 的结果，不取决于你从 1→3→5 还是 1→2→4→5。

最优子结构：大问题的最优解包含小问题的最优解。如果到达台阶 5 的最优路径经过台阶 4，那么到达台阶 4 的部分一定也是到达台阶 4 的最优路径——否则你可以替换成更优的，矛盾。

理论 + 代码

模型一：一维最优化——青蛙跳台阶

$N$ 个台阶，第 $i$ 个台阶高度 $h_i$。从台阶 $i$ 跳到台阶 $j$ 的花费是 $|h_i - h_j|$。每次只能跳 1 或 2 步。求从台阶 1 到台阶 $N$ 的最小花费。

状态：$dp[i]$ = 从台阶 1 到台阶 $i$ 的最小花费。

转移方程：

$dp[i] = \min(dp[i-1] + |h_i - h_{i-1}|,\ dp[i-2] + |h_i - h_{i-2}|)$

初始值：$dp[1] = 0$（已经在起点），$dp[2] = |h_1 - h_2|$（只有一种跳法）。

为什么是对的？到达台阶 $i$ 的最后一步只有两种可能：从 $i-1$ 跳过来，或者从 $i-2$ 跳过来。枚举这两种，取较小的。这就穷尽了所有情况——因为每次只允许跳 1 或 2 步。

#include <cstdio>
#include <algorithm>
using namespace std;

int main() {
    int N;
    scanf("%d", &N);
    int h[100009];
    for (int i = 1; i <= N; i++) scanf("%d", &h[i]);

    int dp[100009];
    dp[1] = 0;                            // ① 起点
    dp[2] = abs(h[1] - h[2]);             // ② 只能从 1 跳过来
    for (int i = 3; i <= N; i++) {
        dp[i] = min(dp[i-1] + abs(h[i] - h[i-1]),   // ③ 从 i-1 跳
                     dp[i-2] + abs(h[i] - h[i-2]));  // ④ 从 i-2 跳
    }
    printf("%d\n", dp[N]);
}

逐行解析：

• ① 起点不用跳，花费 0。
• ② 第 2 个台阶只能从第 1 个跳过来，别无选择。
• ③④ 枚举两种可能的”最后一步”。这里没有遗漏——因为你不可能从 $i-3$ 直接跳到 $i$（规则不允许）。

模拟：$N = 5$, $h = [8, 6, 9, 2, 5]$。

i	h[i]	dp[i-1] + |h[i]-h[i-1]|	dp[i-2] + |h[i]-h[i-2]|	dp[i]
1	8	—	—	0
2	6	—	—	|8-6| = 2
3	9	2 + |9-6| = 5	0 + |9-8| = 1	1
4	2	1 + |2-9| = 8	2 + |2-6| = 6	6
5	5	6 + |5-2| = 9	1 + |5-9| = 5	5

路径：1 → 3 → 5（跳 2 步，跳 2 步），花费 1 + 4 = 5。✓

模型二：二维计数——网格路径

$H \times W$ 的网格，从 $(1,1)$ 走到 $(H,W)$，只能往右或往下。有些格子是障碍。求路径数。

状态：$dp[i][j]$ = 从 $(1,1)$ 走到 $(i,j)$ 的路径数。

转移方程：$dp[i][j] = dp[i-1][j] + dp[i][j-1]$（如果 $(i,j)$ 不是障碍）。

为什么？到达 $(i,j)$ 的最后一步，要么从上方 $(i-1,j)$ 往下走，要么从左方 $(i,j-1)$ 往右走。两种情况不重叠，所以直接相加。

初始值：$dp[1][1] = 1$（如果起点不是障碍）。

#include <cstdio>
using namespace std;
const int MOD = 1000000007;

int main() {
    int H, W;
    scanf("%d%d", &H, &W);
    char grid[1009][1009];
    for (int i = 1; i <= H; i++) scanf("%s", grid[i] + 1);

    int dp[1009][1009] = {};
    dp[1][1] = 1;                                    // ① 起点
    for (int i = 1; i <= H; i++)
        for (int j = 1; j <= W; j++) {
            if (grid[i][j] == '#') { dp[i][j] = 0; continue; } // ② 障碍
            if (i > 1) dp[i][j] = (dp[i][j] + dp[i-1][j]) % MOD; // ③ 从上方
            if (j > 1) dp[i][j] = (dp[i][j] + dp[i][j-1]) % MOD; // ④ 从左方
        }
    printf("%d\n", dp[H][W]);
}

逐行解析：

• ① 起点到起点有 1 条路径（原地不动）。
• ② 障碍格子不可能到达，路径数置 0。
• ③④ 分别从上方和左方累加路径数。注意边界检查（i > 1, j > 1）。

递推 vs 记忆化搜索

上面两种 DP 都是”递推”——从小问题算到大问题，按固定顺序填表。

另一种方式是”记忆化搜索”——从大问题出发递归，遇到已算过的直接返回：

int memo[100009];

int solve(int i) {
    if (i == 1) return 0;
    if (i == 2) return abs(h[1] - h[2]);
    if (memo[i] != -1) return memo[i];        // ① 已算过，直接返回
    return memo[i] = min(solve(i-1) + abs(h[i]-h[i-1]),  // ② 递归算
                          solve(i-2) + abs(h[i]-h[i-2]));
}

两种方式等价，时间都是 $O(N)$。递推通常更快（无递归开销），记忆化更直觉（不用想计算顺序）。实际比赛中，状态转移顺序明确时用递推，图上 DP 或状态间有复杂依赖时用记忆化。

例题

例题 1：M&A 028 — Frog 1

题目：$N$ 个台阶，高度 $h_1, \ldots, h_N$。从台阶 1 出发，每次跳 1 或 2 步，花费 $|h_i - h_j|$。求到达台阶 $N$ 的最小花费。

数据范围：$2 \le N \le 10^5$

—— AtCoder M&A 028

分析：就是上面讲的模型一。直接套模板。

输入样例：

5
8 6 9 2 5

输出：5

代码：

#include <cstdio>
#include <algorithm>
using namespace std;

int main() {
    int N;
    scanf("%d", &N);
    int h[100009];
    for (int i = 1; i <= N; i++) scanf("%d", &h[i]);

    int dp[100009];
    dp[1] = 0;
    dp[2] = abs(h[1] - h[2]);
    for (int i = 3; i <= N; i++)
        dp[i] = min(dp[i-1] + abs(h[i] - h[i-1]),
                     dp[i-2] + abs(h[i] - h[i-2]));
    printf("%d\n", dp[N]);
}

逐行解析：

• 状态 $dp[i]$ = 到达第 $i$ 个台阶的最小花费。
• 转移：枚举最后一步的来源（$i-1$ 或 $i-2$），取最小值。
• 初始值 $dp[1]=0$，$dp[2]=|h_1-h_2|$。
• 复杂度 $O(N)$。

---

例题 2：M&A 031 — Taro’s Vacation

题目：$N$ 天假期，第 $i$ 天有三个活动，幸福值分别为 $a_i, b_i, c_i$。每天选一个活动，相邻两天不能选同一活动。求最大总幸福值。

数据范围：$1 \le N \le 10^5$

—— AtCoder M&A 031

分析：状态需要多加一维——“今天选了哪个活动”。

状态：$dp[i][j]$ = 第 $i$ 天选活动 $j$（$j=0,1,2$）时，前 $i$ 天的最大幸福值。

转移：$dp[i][j] = \max_{k \ne j}(dp[i-1][k]) + \text{value}[i][j]$。昨天选了活动 $k$，今天选活动 $j$，要求 $k \ne j$。

代码：

#include <cstdio>
#include <algorithm>
using namespace std;

int main() {
    int N;
    scanf("%d", &N);
    int a[100009], b[100009], c[100009];
    for (int i = 1; i <= N; i++)
        scanf("%d%d%d", &a[i], &b[i], &c[i]);

    int dp[100009][3];
    dp[1][0] = a[1]; dp[1][1] = b[1]; dp[1][2] = c[1]; // ① 第一天直接选
    for (int i = 2; i <= N; i++) {
        dp[i][0] = max(dp[i-1][1], dp[i-1][2]) + a[i]; // ② 今天选 a
        dp[i][1] = max(dp[i-1][0], dp[i-1][2]) + b[i]; // ③ 今天选 b
        dp[i][2] = max(dp[i-1][0], dp[i-1][1]) + c[i]; // ④ 今天选 c
    }
    printf("%d\n", max({dp[N][0], dp[N][1], dp[N][2]}));
}

逐行解析：

• ① 第一天不需要考虑”昨天选了什么”，三个活动各自独立。
• ②③④ 今天选活动 $j$，昨天只能是另外两个活动之一，取较大的加上今天的幸福值。
• 最终答案：最后一天三个活动取最大值。

模拟：$N=3$，活动值 $(10, 40, 70), (20, 50, 80), (30, 60, 90)$。

天	dp[i][0] (选a)	dp[i][1] (选b)	dp[i][2] (选c)
1	10	40	70
2	max(40,70)+20=90	max(10,70)+50=120	max(10,40)+80=120
3	max(120,120)+30=150	max(90,120)+60=180	max(90,120)+90=210

答案 = max(150, 180, 210) = 210。路径：c(70) → b(120) → c(210)。✓

---

例题 3：TB A25 — Number of Routes（网格路径计数）

题目：$H \times W$ 网格，有些格子是障碍。从 $(1,1)$ 走到 $(H,W)$，只能往右或往下，求路径数。

数据范围：$1 \le H, W \le 1000$

—— AtCoder Tessoku Book A25

分析：模型二的原题。$dp[i][j] = dp[i-1][j] + dp[i][j-1]$。

代码：

#include <cstdio>
using namespace std;
const int MOD = 1000000007;

int main() {
    int H, W;
    scanf("%d%d", &H, &W);
    char grid[1009][1009];
    for (int i = 1; i <= H; i++) scanf("%s", grid[i] + 1);

    int dp[1009][1009] = {};
    dp[1][1] = (grid[1][1] == '.');              // ① 起点不是障碍才有 1 条路
    for (int i = 1; i <= H; i++)
        for (int j = 1; j <= W; j++) {
            if (grid[i][j] == '#') continue;     // ② 障碍跳过
            if (i > 1) dp[i][j] = (dp[i][j] + dp[i-1][j]) % MOD;
            if (j > 1) dp[i][j] = (dp[i][j] + dp[i][j-1]) % MOD;
        }
    printf("%d\n", dp[H][W]);
}

逐行解析：

• ① 如果起点就是障碍，路径数为 0。
• ② 障碍格子的 $dp$ 值保持 0（初始化时已清零），不会贡献给后续格子。
• 答案对 $10^9+7$ 取模。如果题目要求 $998244353$，改 MOD 即可。

---

例题 4：T90 008 — AtCounter（子序列匹配计数）

题目：长度 $N$ 的字符串 $S$，求有多少个子序列（不要求连续）等于 “atcoder”。答案对 $10^9+7$ 取模。

数据范围：$1 \le N \le 10^5$

—— AtCoder Typical 90 008

分析：状态需要两维——“处理了前 $i$ 个字符”和”已经匹配了目标串的前 $j$ 个字符”。

状态：$dp[j]$ = 匹配了 “atcoder” 前 $j$ 个字符的方案数（省略 $i$ 维，用滚动数组）。

转移：遍历字符串 $S$ 的每个字符 $c$。如果 $c$ 等于 “atcoder”[j]，则 $dp[j+1] \mathrel{+}= dp[j]$——新匹配了第 $j+1$ 个字符。

关键：必须倒序枚举 $j$。如果正序，同一个字符 $c$ 可能被多次使用（比如 $c$ = ‘a’，先从 $dp[0]$ 更新 $dp[1]$，然后又从 $dp[1]$ 更新 $dp[2]$），但实际上一个字符只能用一次。倒序避免了这个问题。

代码：

#include <cstdio>
#include <cstring>
using namespace std;
const int MOD = 1000000007;

int main() {
    int N;
    scanf("%d", &N);
    char S[100009];
    scanf("%s", S);
    const char* T = "atcoder";
    int len = strlen(T);

    int dp[8] = {};
    dp[0] = 1;                                  // ① 空串匹配完成，1 种方案
    for (int i = 0; i < N; i++) {
        for (int j = len - 1; j >= 0; j--) {    // ② 倒序！
            if (S[i] == T[j])
                dp[j+1] = (dp[j+1] + dp[j]) % MOD; // ③ 匹配成功
        }
    }
    printf("%d\n", dp[len]);                    // ④ 完整匹配 "atcoder" 的方案数
}

逐行解析：

• ① $dp[0] = 1$：匹配了 0 个字符（空匹配），有 1 种方案——什么都不选。
• ② 倒序枚举 $j$ 确保每个字符只被使用一次。
• ③ 当前字符 $S[i]$ 匹配目标串第 $j$ 个字符，方案数累加。
• ④ $dp[7]$ 是匹配完整 “atcoder”（7 个字符）的方案数。

模拟：$S$ = “aatc”，目标 “at”。

字符	dp[0]	dp[1] (匹配了 ‘a’)	dp[2] (匹配了 ‘at’)
初始	1	0	0
’a’	1	0+1=1	0
’a’	1	1+1=2	0
’t’	1	2	0+2=2
’c’	1	2	2

“at” 出现了 2 次（第 1 个 ‘a’+第 3 个 ‘t’，或第 2 个 ‘a’+第 3 个 ‘t’）。✓

---

例题 5：M&A 029 — Climb Stairs（爬楼梯计数）

题目：$N$ 阶楼梯，每次可以走 1 或 2 步。从第 0 阶走到第 $N$ 阶，有多少种走法？答案对 $10^9+7$ 取模。

数据范围：$1 \le N \le 10^6$

—— AtCoder M&A 029

分析：和青蛙跳台阶的区别在于：这里求的是方案数而非最小花费。转移从 min 变成加法。

状态：$dp[i]$ = 从第 0 阶到第 $i$ 阶的走法数。

转移：$dp[i] = dp[i-1] + dp[i-2]$（最后一步走 1 步或 2 步，方案数相加）。

初始值：$dp[0] = 1$（已经在第 0 阶，1 种走法——不动），$dp[1] = 1$（只能走 1 步）。

这其实就是斐波那契数列！

代码：

#include <cstdio>
using namespace std;
const int MOD = 1000000007;

int main() {
    int N;
    scanf("%d", &N);
    int dp[1000009];
    dp[0] = 1;             // ① 0 阶：1 种走法（不动）
    dp[1] = 1;             // ② 1 阶：只能走 1 步
    for (int i = 2; i <= N; i++)
        dp[i] = (dp[i-1] + dp[i-2]) % MOD;  // ③ 斐波那契！
    printf("%d\n", dp[N]);
}

逐行解析：

• ①② 边界条件。$dp[0]=1$ 是一个常见的约定——“什么都不做”也是一种方案。
• ③ 到达第 $i$ 阶的最后一步要么从 $i-1$ 走上来，要么从 $i-2$ 走上来。走法数相加。

参考文献

教材讲解 — 競技プログラミングの鉄則 第 4 章

• 4.1 B16 Frog 1（一维 DP 最优化 解说）
• 4.2 B17 Frog 1 with Restoration（路径还原 解说）
• 4.7 A16 Dungeon 1（青蛙跳台阶 解说）
• 4.9 A25 Number of Routes（网格路径计数 解说）

基础练习 — アルゴリズムと数学 演習問題集

• 028 Frog 1（青蛙跳台阶）【例题】
• 029 Climb Stairs（爬楼梯计数）【例题】
• 031 Taro’s Vacation（多活动选择 DP）【例题】

系统练习 — 競技プログラミングの鉄則

• A16 Dungeon 1（青蛙跳台阶）
• A17 Dungeon 2（三步跳 DP）
• A21 Block Game（方块取最大值）
• A22 Sugoroku（骰子走格子）
• A23 All Free（全选 DP）
• A25 Number of Routes（网格路径计数）【例题】
• B16 Frog 1（同 M&A 028）
• B17 Frog 1 with Restoration（路径还原）

实战练习 — 競プロ典型 90 問

• 008 AtCounter（★4，子序列匹配计数）【例题】
• 050 Stair Jump（★3，爬楼梯变体）

---

系列索引

第零章 基础工具

• 00-01 复杂度与暴力枚举
• 00-02 排序
• 00-03 累积和与差分

第一章 搜索技术

• 01-01 二分搜索
• 01-02 双指针与尺取法

第二章 数学基础

• 02-01 整数与整除
• 02-02 素数与筛法
• 02-03 同余与模运算
• 02-04 快速幂与逆元
• 02-05 组合计数
• 02-06 容斥原理
• 02-07 欧拉函数
• 02-08 博弈论基础

第三章 数据结构

• 03-01 栈、队列与单调栈
• 03-02 堆与优先队列
• 03-03 并查集
• 03-04 树状数组
• 03-05 线段树
• 03-06 懒标记线段树
• 03-07 Sparse Table 与倍增
• 03-08 字符串哈希

第四章 图论

• 04-01 图的遍历
• 04-02 最短路—Dijkstra 与 01-BFS
• 04-03 最短路—Bellman-Ford 与 Floyd
• 04-04 拓扑排序
• 04-05 最小生成树
• 04-06 强连通分量与 2-SAT
• 04-07 二分图与网络流
• 04-08 树上问题

第五章 动态规划

• 05-01 DP入门—状态与转移
• 05-02 背包问题族
• 05-03 LIS、LCS与编辑距离
• 05-04 区间DP
• 05-05 状态压缩DP
• 05-06 树形DP与数位DP
• 05-07 矩阵快速幂与线性递推

第六章 贪心

• 06-01 贪心策略与交换论证
• 06-02 区间调度与优化

第七章 字符串

• 07-01 字符串哈希详述
• 07-02 后缀数组

第八章 进阶

• 08-01 卷积与FFT
• 08-02 期望与概率
• 08-03 Zeta / Möbius 变换
• 08-04 计算几何基础
• 08-05 采样与随机化