DP大师 · 总纲

动态规划 · 通用方法论

先把框架立起来，再进七大家族——学会用一张逐格填写的表，装下指数级的搜索。

动态规划在做什么

一句话：把一个大问题拆成许多重叠的子问题，每个子问题只算一次、把答案记下来， 后面遇到就直接查表。它介于两种极端之间——暴力搜索把所有可能都试一遍（常是 2n2^n 或 n!n! 级），贪心每步只顾眼前最优（快，但常常错）。DP 用「记忆」换「重复」，把暴力的指数压成多项式，又比贪心稳。

所以判断一道题「能不能 DP」，本质是问三件事：子问题的最优能不能拼出大问题的最优？ 一个局面定下来后，还需不需要回头看它是怎么来的？这些子问题会不会反复出现？ 三个「是」，就是下面的三个前提。

能用 DP 的三个前提

① 最优子结构

大问题的最优解，由它子问题的最优解拼成。比如「前 ii 件、容量 jj 的最优」， 一定建立在「前 i−1i-1 件」的最优之上——否则把更优的子解换进来，整体还能更优，矛盾。

② 无后效性

一个状态一旦确定，后续决策只看这个状态本身，与「它是经由哪条路径到达的」无关。 这让我们可以只记状态、不记历史。若「怎么来的」会影响未来，就得把那部分信息补进状态维度里。

③ 重叠子问题

同一个子问题会被反复用到。正因为重叠，「算一次、记下来」才划算——这也是 DP 区别于分治的地方 （分治的子问题通常互不相交）。

解一道 DP，就这五步

拿到题别急着写循环，按这五步想清楚，代码几乎是抄出来的：

1
定状态。用最少的维度，把「当前局面」不重不漏地描述出来。问自己：有几样东西在变？每样就是一维。dp[⋯ ]dp[\cdots] 的含义要一句话说得清（例：以 ii 结尾的最长上升子序列长度）。
2
写转移。盯住最后一步决策：当前状态是从哪些更小的状态、付出什么代价得到的？把它们取 max⁡/min⁡/∑\max/\min/\sum。
3
定边界与初值。最小的子问题答案是什么？没被转移覆盖的格子要手动填对（求最大常填 00 或 −∞-\infty，计数填 00 而起点填 11）。
4
定递推顺序。保证算 dp[x]dp[x] 之前，它依赖的子状态都已算好——见下一节。
5
取答案。答案未必是最后一格，可能是某一维的最值（如 LIS 取 max⁡idp[i]\max_i dp[i]）。想清楚要读哪个/哪些格子。

状态：DP 的灵魂

九成的 DP，难在状态怎么定，而非转移。维度 = 有几个「限制/进度」在同时变化： 背包是「考虑到第几件」×「用了多少容量」，于是 f[i][j]f[i][j]；区间 DP 是「左右端点」，于是 f[l][r]f[l][r]； 树形 DP 是「以谁为根的子树」×「选没选它」，于是 f[u][0/1]f[u][0/1]。

两条经验：状态要刚好够用——少一维会漏信息（无后效性被破坏），多一维会白白拖慢； 当「怎么来的」影响未来时，把它编码进状态（比如上一步选了什么、当前奇偶、集合用二进制压成一个整数）。

转移：从子问题推当前

写转移的通用姿势，是枚举「最后一步」的所有可能决策，在对应的更小状态上取最优：

dp[s]=opt⁡s ← s′( dp[s′]+cost(s′→s) )dp[s]=\operatorname*{opt}_{s\,\leftarrow\,s'}\big(\,dp[s']+\text{cost}(s'\to s)\,\big)

这里 opt\text{opt} 按题意是 max⁡\max、min⁡\min 或求和 ∑\sum（计数）。 把「最优」换成「累加」，最优 DP 就变成计数 DP；同一套状态与转移骨架，常能一题多吃。

递推顺序：先算谁

铁律：算 dp[x]dp[x] 前，它依赖的每个子状态必须都已经算好。顺序错了，你读到的是没填好的空格。三种常见姿势：

→
按维度顺推。线性 DP 从小到大扫下标；区间 DP 按区间长度从短到长（短区间先算，长区间才能用）。
↑
后序遍历。树形 DP 自底向上——先把所有孩子的子树算完，再合并到父亲。
↺
记忆化搜索。懒得推顺序？写成递归 + 备忘录，让递归调用天然保证「依赖先算」——它就是自顶向下的 DP。
记忆化搜索 · 通用模板
int f[N];                 // 备忘录，-1 表示"尚未计算"
bool vis[N];

int dp(int s)             // 求状态 s 的答案
{
    if (vis[s]) return f[s];        // 算过就直接查表，绝不重算
    vis[s] = true;
    int res = BASE;                 // 边界 / 初值
    for (auto &d : decisions(s))    // 枚举"最后一步"的决策
        res = max(res, dp(prev(s, d)) + cost(d));
    return f[s] = res;
}

记忆化 = 自顶向下的 DP

递推是「自底向上」填表，记忆化是「自顶向下」递归 + 缓存。两者算的是同一批状态、同一个转移，只是谁先谁后的组织方式不同。状态空间稀疏、或顺序难推时，记忆化往往更好写。

空间优化：把一维滚掉

当 dp[i][⋅]dp[i][\cdot] 只依赖 dp[i−1][⋅]dp[i-1][\cdot]，就没必要保留所有行——用一维数组就地更新，空间从 O(nm)O(nm) 降到 O(m)O(m)。

滚动数组 · 01 背包一维
// 01 背包压成一维：f[j] = 容量恰为 j 时的最大价值
int f[M + 1] = {0};
for (int i = 1; i <= n; i++)
    for (int j = m; j >= w[i]; j--)        // ★逆推：先算大 j
        f[j] = max(f[j], f[j - w[i]] + v[i]);

// 完全背包：同一段转移，内层改成正推即可（每件可无限取）
// for (int j = w[i]; j <= m; j++) ...

降维后，循环方向决定物种

压成一维后，正 / 逆序决定你读到的是「上一层的旧值」还是「本层已更新的新值」：01 背包逆推（每件至多一次）， 完全背包正推（每件无限次）。同一段转移，方向反了就是另一道题。

调试与常见陷阱

1
打印整张表。DP 错了先别改代码，把 dpdp 数组打出来逐格对照手算——错在哪一格，一眼看见。
2
对拍。写个 O(2n)O(2^n) 暴力，用小数据随机对拍 DP，最快揪出转移或边界的偏差。
3
初值与边界。「求最大」忘了把不可达状态设成 −∞-\infty、计数忘了 dp[0]=1dp[0]=1，是最高频的错。
4
溢出与越界。方案数、代价和很容易爆 int，果断上 long long；一维逆推注意 j≥wij\ge w_i 的下界。

七大家族速览

框架立好了，就进具体家族。每个家族其实是一类状态设计的范式——认出题目属于哪一类，状态怎么定就有了模板：

A背包 DP9B线性 DP7C区间 DP5D矩阵 DP2E换根 DP4F树形 DP5G状压 DP5

已进入 通用方法论 · DP大师