动态规划的本质：状态 + 转移，不是背模板

栏目：算法深读 🔵 | 教练亲笔 | 第 02 篇

很多学生学信奥，栽在动态规划（DP）上。

我去年带过一个初二的孩子，背"背包九讲"背得滚瓜烂熟——0-1、完全、多重、分组的模板代码，他能默写。给他一道新题，换个包装，他就懵：老师，这是不是 DP？是哪种 DP？状态怎么设？转移怎么写？

他说：我背了那么多模板，为什么还是不会做？

我跟他说：你背的是"答案"，不是"问题"。动态规划从来不是关于"哪种模板"，是关于两个东西——状态和转移。

今天这篇文章，帮你把 DP 的本质讲透。看完之后，你会发现：所有 DP 题，都在问同一件事。

一、先破一个执念：DP 不是"算法"，是"思路"

很多教材把 DP 归类为"算法"，和"排序"、"搜索"并列。这是误导。

排序是固定的流程：拿到一组数，比较、交换、循环几轮，结束。不管什么数据，框架不变。

DP 不是。DP 是一类思维方法——把大问题拆成小问题，把答案存起来，避免重复算。

它的核心从来不是"代码长什么样"，而是两件事：

1. 状态是什么（你用哪些变量去描述"做到哪儿了"）
2. 转移是什么（从状态 A 到状态 B，靠什么关系）

只要这两件事定下来，代码就是机械的填空。

金句一：DP 的难度 80% 在"想到"，20% 在"写出来"。学生搞反了。

二、DP 三件套：状态、转移、初始化

我给学员讲 DP，永远先讲这三件套。任何 DP 题，剥开包装，里面都是这个结构。

1. 状态：用一个数组描述"做到哪儿了"

状态是 DP 的灵魂。

什么叫状态？状态就是"我现在关心的那件事"。

举几个例子：

• 0-1 背包：状态是"前 i 个物品、容量 j 的情况下，最大价值是多少"。dp[i][j]。
• 最长上升子序列（LIS）：状态是"以第 i 个数结尾的最长上升子序列长度"。dp[i]。
• 最短路径计数：状态是"从起点走到格子 (i, j) 有多少种走法"。dp[i][j]。

看出来了吗？状态的本质是用有限的数字，把"我做到哪一步"这件事说清楚。

初学者最常犯的错：状态描述得不准确。比如 0-1 背包，状态写成"前 i 个物品的最大价值"——少了"容量 j"。这就是不准确，转移的时候会发现少了一个维度，写不下去。

金句二：状态对了，转移自然就出来了；状态错了，转移写得再花哨也是错的。

2. 转移：从"小问题"推导"大问题"

转移方程，就是"大问题"和"小问题"之间的关系。

继续用 0-1 背包说：

• 状态：dp[i][j] = 前 i 个物品、容量 j 时的最大价值
• 转移：第 i 个物品选不选？ 
• 不选：dp[i][j] = dp[i-1][j]
• 选：dp[i][j] = dp[i-1][j-w[i]] + v[i]（前提是装得下，j ≥ w[i]）
• 取两者最大值

看出来没？转移的本质是把"第 i 个物品"的影响去掉，回到"前 i-1 个物品"的状态，再加上它自己的贡献。

所有的 DP 转移，都是这个套路：把"当前选择"剥掉，回到"更小一档的状态"，再加加减减。

3. 初始化：边界不能忘

很多学生转移方程写得出来，一跑代码就错——九成是初始化没做对。

初始化有两件事：

1. 明确 dp[0][...] 或 dp[...][0] 的值（边界）
2. 把不合法状态标成"无穷小"或"无穷大"，避免污染答案

比如 0-1 背包：

• dp[0][j] = 0（0 个物品，价值自然是 0）
• 其它位置可以初始化为 0（因为求最大值，0 不会污染），但求最小值时，初始化必须是"无穷大"。

金句三：初始化不是"补充"，是"定义游戏规则"。规则没定对，后面全错。

三、用一道真题走一遍流程

光说不练假把式。我用 洛谷 P1216 数字三角形 当例子，完整走一遍。

题目（简化版）

一次比赛中，有 n 个选手依次提交，评委给出每个人的分数。已知第 i 个选手的分数是 s[i]。

直播要展示当前已提交选手的前 ⌊i × w%⌋ 名（i 是当前人数，w 是给定的百分比，比如 60）。

对每个 i，求出第 i 个时刻，展示名单中的最低分数。

输入：n, w 和分数数组。输出：每个时刻的展示最低分。

第 1 步：定义状态

例子：洛谷 P1216 数字三角形

        7      3   8    8   1   0  2   7   4   44   5   2   6   5

从顶走到底，每次只能走到左下或右下，求经过数字之和最大的路径。

状态

dp[i][j] = 走到第 i 行第 j 列时的最大路径和。

转移

从哪儿走到 (i, j)？要么从 (i-1, j-1)，要么从 (i-1, j)。

dp[i][j] = max(dp[i-1][j-1], dp[i-1][j]) + a[i][j]

初始化

dp[1][1] = a[1][1]，其它初始为 0（这里 0 不会污染答案，因为数字都是非负的；如果有负数，要初始化为 -∞）。

代码（带逐行注释）

#include<bits/stdc++.h>usingnamespace std;constint N = 105;int a[N][N];   // 存三角形数字int dp[N][N];  // dp[i][j] = 走到(i,j)的最大路径和intmain(){int n;    cin >> n;// 读入三角形for (int i = 1; i <= n; i++) {for (int j = 1; j <= i; j++) {            cin >> a[i][j];        }    }// 初始化：起点    dp[1][1] = a[1][1];// 状态转移：从上往下走for (int i = 2; i <= n; i++) {for (int j = 1; j <= i; j++) {// 错误写法（很多初学者栽在这）：// dp[i][j] = max(dp[i-1][j-1], dp[i-1][j]) + a[i][j];// 当 j == 1 时，dp[i-1][0] 越界！if (j == 1) {// 左边是边界，只能从 (i-1, 1) 来                dp[i][j] = dp[i-1][j] + a[i][j];            } elseif (j == i) {// 右边是边界，只能从 (i-1, i-1) 来                dp[i][j] = dp[i-1][j-1] + a[i][j];            } else {// 中间位置，从两个方向选大的                dp[i][j] = max(dp[i-1][j-1], dp[i-1][j]) + a[i][j];            }        }    }// 答案在最后一行，找最大值int ans = 0;for (int j = 1; j <= n; j++) {        ans = max(ans, dp[n][j]);    }    cout << ans << endl;return0;}

常见错误

1. 越界没处理：第一列和最后一列的转移只有一个来源，不写 if 单独判断就 RE（运行错误）。
2. 初始化错位：从 dp[0][0] 开始读入数据，导致索引全错。
3. 答案位置写错：本题答案在最后一行，不是在 dp[n][n]（很多人栽在这）。

四、DP 学习的三个台阶

讲了这么多，给你三个具体的台阶，照着练就够：

台阶 1：先死磕 5 道经典题

1. 0-1 背包（洛谷 P1048 采药）—— 一维 DP 入门
2. 最长上升子序列（洛谷 B3637）—— 单序列 DP
3. 数字三角形（洛谷 P1216）—— 二维 DP
4. 最长公共子序列 LCS（洛谷 P1439）—— 字符串 DP
5. 完全背包（洛谷 P1616 疯狂的采药）—— 0-1 背包的变体

每道题至少做 3 遍：

• 第 1 遍：看题解，照着写
• 第 2 遍：关掉题解，自己写
• 第 3 遍：换一道类似的题（比如把 0-1 背包换成"分割等和子集"），独立做

台阶 2：每个题都问自己"状态是什么"

拿到一道新 DP 题，第一反应不是"这是哪种 DP"，而是：

• 我要回答什么问题？（决定最终状态）
• 这个问题的"参数"是什么？（决定 dp 数组的维度）
• 状态怎么从"小"变到"大"？（决定转移方向）

比如最长回文子序列：状态是 dp[i][j] = s[i..j] 的最长回文子序列长度。转移：dp[i][j] = s[i]==s[j] ? dp[i+1][j-1]+2 : max(dp[i+1][j], dp[i][j-1])。

你会发现一旦状态定下来，转移是"自然"出来的。这就是自顶向下的 DP 思维。

台阶 3：把"备忘录"和"递推"打通

记忆化搜索（自顶向下）和递推（自底向上）本质上是一回事。

记忆化搜索的好处是思路直接、不用操心初始化顺序——你只管递归，递归树自动告诉你"小问题先算"。

递推的好处是常数小、空间可控——因为你能手动压维（比如 0-1 背包把二维压成一维）。

我建议初学者先学记忆化搜索。等你熟练了，再转递推。两种都要会，但思维顺序是"自顶向下 → 自底向上"。

五、写给学员的话

DP 是信奥里第一个真正的"分水岭"。

过了这关，后面的题都能靠"建模 + 转移"走通；过不了，赛场上一半的题你都做不出来。

我自己的经验：DP 不是靠刷题量堆出来的，是靠想清楚状态这一件事想出来的。

每道 DP 题，做完之后问自己三个问题：

1. 状态是什么？为什么是这几个维度？
2. 转移怎么来的？小一档的状态是什么？
3. 初始化是什么？为什么这样设？

回答清楚，DP 就学明白了。

六、本篇金句合集（建议截图保存）

• DP 的难度 80% 在"想到"，20% 在"写出来"。学生搞反了。
• 状态对了，转移自然就出来了；状态错了，转移写得再花哨也是错的。
• 初始化不是"补充"，是"定义游戏规则"。规则没定对，后面全错。

七、配套练习推荐

建议节奏：每天一题，2 周内全部独立完成（不参考代码，只参考思路），DP 思维就基本入门了。

看完这篇文章，如果你家孩子也在走信奥这条路，或者你正在为规划、赛事、学习方法发愁，欢迎扫码加入本地信奥家长群。群里主要交流信奥规划、赛事信息和学习难题，大家互通经验，少走弯路，群内禁广告，专注交流。