HAO的DP先解释一下这里的DP是 Dynamic Programming也就是动态规划不是显示器上那个 DPDisplayPort接口也不是更新DP固件的那个 DP。每次我发这种标题都有人问是不是写错了。动态规划这东西网上已经有一堆教程和题解但大多数人的状态是这样的题解看得懂换一道题又不会模板背得下来一但题目数据范围变大、加上优化要求立刻懵。这篇就是把我自己整理HAO的DP这套笔记时沉淀下来的东西梳理一遍——从最底层的状态设计到线性DP、树形DP、数位DP再到单调队列、四边形不等式、wqs二分这类优化手段最后是调试DP代码时最容易坑人的细节。适合谁看准备笔试面试的、打算法竞赛的、自学DP卡了一周以上的都可以。我会尽量用为什么这样想能想通的方式来讲而不是贴一堆题解让你自己悟。重点不是我抄了什么模板而是每个模板到底在解什么题、什么时候能用、什么时候不能硬套。1. 写DP之前先把三件事想清楚状态是什么转移怎么写循环怎么走很多DP题做不出来不是因为不懂状态压缩、不懂优化而是连最基础的状态定义都没想明白就开始写转移方程写一半发现推不出来又回去改状态。实际上一道DP题拿到手你只需要依次回答三个问题状态是什么转移方程是什么计算的顺序是什么1.1 本质是DAG上的路径规划理解动态规划最有用的一句话是DP本质是在一张有向无环图DAG上做路径规划。把每个状态当成一个节点每次转移当成一条有向边。比如经典的斐波那契数列状态就是第i个数这个节点边就是f[i] f[i-1] f[i-2]这条从 i-1、i-2 指向 i 的边。因为每个节点只依赖它前面的节点图上没有环所以我们可以按照拓扑序把答案逐一算出来。为什么强调无环因为你一旦在图上绕了圈就会鬼打墙dp[i]要等dp[i]自己才能算出来永远没有尽头。这也是无后效性的本质当前状态一旦确定之后的决策就再也不需要关心当前状态是怎么来的。有向无环保证了这一点。我拿通勤举个生活化的例子。你早上从家出发去公司路上要经过若干个地铁站每个站可以换乘不同线路。你只关心到达下一站的时间最早是多少而不需要关心我前一条路是怎么走来的。这就是无后效性。最优子结构则是如果到达每一站的时间都是最早那最终到达公司的组合起来也是最最早。DP能成立依赖的就是这两条性质。1.2 状态设计的一个抓手看数据和看约束新手最迷茫的就是状态怎么设计。我的经验是状态通常藏在两个地方题目给的数据维度。数组长度、剩余次数、当前走到的位置、当前选了哪些物品这些都是天然的状态维度。题目里的约束条件。比如不能连续偷两家那你就得在状态里记录上一家偷了没比如最多交易K次那你就得把交易次数作为一个维度。举个例子打家劫舍这题数组nums[i]表示第i家的金额约束是相邻两家不能同时偷。如果不记录上一家的状态你没法判断第i家能不能偷所以状态至少得是dp[i][0/1]表示偷到第i家且第i家不偷/偷时的最大收益。这比dp[i]直接表示偷到第i家的最大收益要清晰得多因为后者没法回答第i-1家偷没偷这个关键问题。1.3 填表、刷表、记忆化搜索到底用哪种同样是DP写法上有三种流派填表法、刷表法、记忆化搜索。填表法考察当前状态dp[i]是哪些状态转移来的主动查前面的格子把它填上。刷表法从当前状态dp[i]出发去更新它能到达的所有未来的状态。记忆化搜索直接用递归函数写转移加一个缓存数组。本质上和填表法等价但是书写顺序符合直觉而且天然解决拓扑序。我的判断标准很简单当转移顺序不好找、或者状态维度很多时用记忆化搜索当转移形式规整、可以套滚动数组优化时用填表法。举个典型例子数位DP几乎人人都用记忆化搜索就是因为它的状态里有是否贴住上界是否有前导零这种枚举顺序带来的标记用递推写又丑又容易错用递归加缓存写则一气呵成。后面第五部分我会给数位DP的完整模板。也有人会说记忆化搜索有递归栈开销超大规模状态会不会慢实际上在竞赛环境下只要不是状态量上亿的极端情况差距远没有你想象中大。很多时候记忆化搜索被诟病慢不是因为递归本身而是因为你的状态设计里混入了大量用不到的转移。真到了需要极致性能时自然会去写递推加滚动数组但你一开始根本不必为了省那点常数去牺牲可读性。2. 线性DP与状态机DP笔试面试里最常出现的两类线性DP是入门必做状态转移只沿着某个一维方向推进。它本身不难但很多经典算法本质都是线性DP值得你停下来重新审视。2.1 LIS从O(n²)到O(nlogn)二分解法到底优化了什么最长上升子序列LIS是线性DP的必修课。暴力 DP 写法很直白#include bits/stdc.h using namespace std; int main() { int n; cin n; vectorint a(n); for (int i 0; i n; i) cin a[i]; vectorint dp(n, 1); // dp[i]: 以 a[i] 结尾的最长上升子序列长度 int ans 1; for (int i 0; i n; i) { for (int j 0; j i; j) { if (a[j] a[i]) { dp[i] max(dp[i], dp[j] 1); } } ans max(ans, dp[i]); } cout ans \n; return 0; }复杂度 O(n²)n 到 1e5 就撑不住了。这时候需要二分解法。它维护的不是 dp 数组而是一个单调递增的辅助数组tails其中tails[k]表示长度为 k1 的上升子序列中结尾元素可以取到的最小值。这个最小结尾思路非常关键——同样是长度3的子序列结尾是 5 的肯定比结尾是 9 的更有潜力因为 9 后面能接上的数5 一定也能接。于是每读到一个数x就在 tails 里二分找到第一个大于等于 x 的位置把它替换成 x。#include bits/stdc.h using namespace std; int main() { int n; cin n; vectorint a(n); for (int i 0; i n; i) cin a[i]; vectorint tails; // tails[k]: 长为 k1 的上升子序列的最小结尾 for (int x : a) { auto it lower_bound(tails.begin(), tails.end(), x); if (it tails.end()) { tails.push_back(x); } else { *it x; } } cout tails.size() \n; return 0; }注意tails.size()给出的是长度不是那个具体的子序列。如果你需要还原整个子序列得额外开一个数组记录每个数在 tails 里的位置然后从后往前回溯。这个细节很多人忽略面试官如果追问你答不上来就露馅了。这个二分的写法本质上就是把DP转移里在所有 ji 且 a[j]a[i] 的状态中选择最优这一步利用单调性加速到了 O(logn)。2.2 最大连续子段和Kadane算法也是DP最大连续子段和Maximum Subarray很多人直接当贪心背模板了其实它就是最朴素的线性DPdp[i] max(a[i], dp[i-1] a[i])dp[i]表示以a[i]结尾的连续子段的最大和。如果前面一堆数加起来还不如我自己大那就果断从a[i]重新开始。这题提醒我们一件事DP 不一定要写成表格的样子Kadane算法在形式上只有一两个变量但骨子里还是一个标准DP。面试的时候如果能主动说一句这题本质是一个线性DP当前状态只依赖前一个状态会比直接甩代码给面试官印象深刻得多。2.3 状态机DP股票买卖和打家劫舍的统一写法状态机DP是线性DP的进阶特征是状态本身就代表目前处于什么情况。最典型的例子是买卖股票系列的最多完成一笔交易vectorvectorint dp(n, vectorint(2, 0)); // dp[i][0]: 第 i 天结束手里没有股票的最大收益 // dp[i][1]: 第 i 天结束手里持有一支股票的最大收益 dp[0][1] -prices[0]; for (int i 1; i n; i) { dp[i][0] max(dp[i-1][0], dp[i-1][1] prices[i]); // 卖出或在观望 dp[i][1] max(dp[i-1][1], -prices[i]); // 一直持有或今天买入 }为什么买入时的收益是-prices[i]因为你只能交易一次买入那一刻的收益就是负的股价不能再叠加之前的什么收益。这就是状态机的约束所在。打家劫舍大同小异状态就是上一家抢没抢。其实这种状态机DP可以用滚动数组压掉一维每次只需要保留上一天的几个状态变量。题目一旦出现最多完成K笔交易这种限制只需把状态改成dp[i][k][0/1]这就同时考察了状态设计里增加约束维度的能力。到这里你会发现线性DP的题虽然变化多但解法骨架是固定的搞清楚状态维度想明白当前状态可以从哪些前置状态来再确定遍历顺序。真正容易翻车的反而是后面的树形DP和优化算法。3. 树形DP和树上背包能玩明白DFSDP就成功了一半树形DP顾名思义是在树上做DP。树的天然递归结构几乎意味着你都要依赖DFS来遍历。听到树形DP模板很多人的第一反应是背代码但我建议先理解一个底层逻辑树的子树天然把问题分解成了若干子问题所以自底向上的回溯过程就是填表过程。3.1 基本套路先递归子树再回溯更新父节点最经典的入门题是没有上司的舞会或者叫树上最大权独立集每个节点有一个权重选了一个节点就不能选它的直接子节点问能选到的最大权重和。#include bits/stdc.h using namespace std; const int N 200005; vectorint g[N]; long long dp[N][2]; int w[N]; void dfs(int u, int fa) { // 初始化选 u 的收益是 w[u]不选 u 的收益先当 0 dp[u][0] 0; dp[u][1] w[u]; for (int v : g[u]) { if (v fa) 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; for (int i 1; i n; i) cin w[i]; for (int i 1; i n; i) { int u, v; cin u v; g[u].push_back(v); g[v].push_back(u); } dfs(1, 0); cout max(dp[1][0], dp[1][1]) \n; return 0; }这里的核心是父节点状态的计算必须等到所有孩子节点都算完。DFS 天然保证了这一点——先递归深入再在函数返回后进行状态合并。很多树形DP做错是因为在进入孩子节点之前就去更新父节点状态顺序反了后面的孩子还没算完父节点已经被污染了。3.2 换根DP一锤子DFS算不出来的问题就做两次有些树上DP问题要求你对每一个节点都计算答案。比如树上每个点到其他所有点的距离之和。如果你对每个点都做一次DFS然后求距离和复杂度是 O(n²)n 稍微一大就爆炸。换根DP就是为了把这类问题压成 O(n)。思路是两轮DFS第一轮随便选个根比如节点1DFS一遍算出一个基准答案——比如以1为根时每个节点的子树大小以及所有点到1的距离之和。第二轮利用父节点的答案推导子节点的答案。假设我们已知所有节点到 u 的距离和现在要把根从 u 换到儿子 v。那么 v 的子树里的节点每个都离 v 近了 1其他节点每个都远了 1。如果令sz[v]为 v 子树的大小n - sz[v]就是其余节点数那么ans[v] ans[u] - sz[v] (n - sz[v])这公式一眼看穿比背模板强得多。换根DP最容易错的地方是第二轮需要时刻记得此时dp数组存的已经不是以某个点为根的子树状态了而是以全树为根、当前点作为新的根时的全局答案。概念不清晰公式推着推着就乱了。3.3 树上背包容量循环别写反树上背包是从树形DP延伸出来的典型题是选课每门课可能有先修课选一门课之前必须选它的先修课给定总选课门数限制问最大总学分。状态定义为dp[u][j]在以 u 为根的子树里恰好选了 j 门课能获得的最大学分。对于当前节点 u你可以决定选几个孩子里的课程。合并孩子 v 时的转移for (int j size[u]; j 1; --j) { // 枚举当前已经合并的课程数量倒序 for (int k 1; k size[v]; k) { // 枚举从孩子 v 里选 k 门课 if (j - k 0) { dp[u][j] max(dp[u][j], dp[u][j - k] dp[v][k]); } } }两个易错点。第一合并孩子的循环要倒序枚举j不然当前孩子 v 的dp[v][k]可能会被外层循环的新值覆盖导致同一棵子树被选多次。第二循环上界记得用当前子树的实际大小size[u]、size[v]而不是直接用总容量m否则会白白引入无数无效转移复杂度也会退化成 O(nm²)。4. 优化三板斧单调队列、四边形不等式、二分到底分别解决什么问题DP 题做到一定量你就会碰到状态定义很简单但转移复杂度爆炸的题目。这时候需要优化。单调队列优化DP四边形不等式优化DP二分答案/带权二分是三类最常见的优化思路。它们的共同点是不是改变状态定义而是让每次找最优转移的速度更快。4.1 单调队列优化当转移来源像一个滑动窗口时单调队列优化的适用场景非常具体状态转移方程形如dp[i] min/max ( dp[j] cost(i, j) )且j的取值范围是一个连续区间[i - k, i - 1]这个区间随着 i 的增大单调向右滑动。最经典的例子是滑动窗口取最大值。单调队列里保存的是下标不是值。队列里边的人下标递增对应的 dp 值也保持单调。每次转移之前做三件事把队头中已经滑出窗口的过期下标弹出把当前新下标按值更优的原则从队尾挤掉取队头作为最优转移来源。我见过太多人栽在第 1 步上。顺序必须是先弹过期下标再维护单调性然后取队头。很多人先取队头发现取出来的已经过期然后又忘记回去检查下一个直接导致答案错误。标准模板长这样dequeint q; // 存下标 for (int i 1; i n; i) { while (!q.empty() q.front() i - k) q.pop_front(); // 1. 弹出过期下标 // 这时队头就是合法区间内的最优转移来源 if (!q.empty()) dp[i] dp[q.front()] w[i]; while (!q.empty() dp[q.back()] dp[i]) q.pop_back(); // 2. 维护单调性 q.push_back(i); // 3. 入队 }这个模板你要是能背下来并且真正理解队头弹出、队尾维护的顺序基本就到手了。要注意的是不是所有看起来像滑动窗口的题都能用单调队列。要求窗口中每个元素的参与方式是统一的如果 cost 里还混着和当前 i 有关的二次项那可能是斜率优化而非单调队列的适用范围。4.2 四边形不等式与决策单调性区间DP的降维魔法区间DP的经典转移长这样dp[i][j] min( dp[i][k] dp[k1][j] cost(i, j) ) // i k j这个转移本身就要枚举 k加上区间枚举整体 O(n³)。n 到 2000 以上就承受不住了。这时候四边形不等式如果能用就可以大砍一刀。四边形不等式的含义用通俗的话说当区间变宽时最优决策点不会往左退只会往右走。体现在代码上我们开一个数组opt[i][j]记录 dp[i][j] 取得最优解时 k 的位置如果满足四边形不等式会有opt[i][j-1] opt[i][j] opt[i1][j]于是枚举 k 时不需要从 i 到 j-1 全扫只需要在[opt[i][j-1], opt[i1][j]]里扫。这就是为什么四边形不等式优化也叫决策单调性优化。用它之前你得确认代价函数cost(i, j)满足四边形不等式和单调性最经典的判定是区间DP里的石子合并一类问题合并代价满足四边形不等式。实操中我一般会先写一个朴素版用小数据验证opt数组是不是单调的确认单调了再上优化——这样能避免背错条件白忙活。另外如果最优决策点是单调的还有一种配套优化叫分治法。它适合的状态定义更复杂、不适合存opt二维数组的场景思路是把需要计算的状态按下标区间分治每次递归只需要尝试一半以内的决策点。分治法和决策单调性通常是绑定出现的遇到dp[i][j] min(dp[i-1][k] cost(k1, j))这类长得很像的两段式DP分治优化往往是最优选。4.3 wqs二分带权二分解决恰好选 K 个的最优化问题二分和DP的关系不只出现在LIS那种在有序数组里找插入位置的场景。有很多DP题答案是恰好选 K 个时的最优值直接作为一个维度放进状态里会太大但暴力枚举数量又不行。如果这个问题满足一个性质答案关于数量 K 的图像是一个凸函数或凹函数那么你可以给每次选择增加一个惩罚项 price。这样原问题变成一个不限制数量的新问题每次只需通过DP求出在附加了 price 之后的最优方案和最优数量然后二分 price让最优数量逼近 K。打个比方你本来要恰好买10个苹果现在商家说买一个苹果额外收x元你重新算怎么买最划算如果最优购买数是8说明x罚得太重应该减小x如果最优购买数是15说明罚得不够应该增大x。二分x直到最优购买数是10。最终答案就是附加x时DP算出的最优值减去 K*x。这套技巧在竞赛里叫wqs二分或带权二分。最容易踩的坑是题目答案函数并不真的是凸函数或者你在二分边界上差一个单位。我建议正式提交前先在小数据上暴力验证几个 K 对应的最优值确认凸性再上wqs二分。5. 数位DP与动态DP当你觉得普通DP不够用的时候线性DP和树形DP解决的是状态结构清晰、转移方式固定的题目。但有两类DP它们的难点不在转移优化而在状态设计本身数位DP和动态DP。5.1 数位DP记忆化搜索比递推好写一百倍数位DP解决的是统计一个区间内满足某种数字性质的数的个数这类问题。例如统计[L, R]中有多少个数不包含数字 4 和 7。直接枚举每个数再检查R 一上来就超时数位DP按每一位来做DP。核心状态是pos当前枚举到哪一位、limit前面是否已经和上界完全相等能否自由填数字、以及题目要求的性质状态。用记忆化搜索写十分直接long long dfs(int pos, bool limit, bool lead, ...) { if (pos 0) return 1; // 所有位都填完了且没违反约束 if (!limit !lead memo[pos] ! -1) return memo[pos]; int up limit ? digit[pos] : 9; long long res 0; for (int d 0; d up; d) { if (d 4 || d 7) continue; // 不能包含 4 和 7 res dfs(pos - 1, limit d up, lead d 0, ...); } if (!limit !lead) memo[pos] res; return res; }两个关键点。第一memo只在!limit !lead时才缓存。因为一旦limit和lead为真这组状态是特殊的、和其他数位组合并不等价不能通用缓存如果你强行缓存会导致上下界不同的情况互相污染答案错得莫名其妙。第二dfs的答案是从低位到高位递归的初始化调用时limittrue, leadtrue。数位DP的区间[L,R]答案分别算cal(R)-cal(L-1)即可。5.2 动态DP把转移过程喂给线段树动态DPDynamic DP简称DDP听起来高大上但核心思想一句话把DP的每一步转移写成矩阵乘法然后用线段树等数据结构对连续转移做批处理。为什么可以这么搞因为矩阵乘法虽然不满足交换律但满足结合律。所以如果一次DP转移能被写成左乘一个矩阵那么连续若干步的DP就等价于左乘这些矩阵的乘积。于是当你需要支持修改某一个位置的权值并快速重算整条链上的DP答案时线段树就能在 O(logn) 时间更新矩阵乘积。树上的动态DP比如动态维护树上最大权独立集支持单点修改权值需要用到树链剖分把树变成若干条链每条链内维护转移矩阵。这块我坦白说学起来难度陡增适合在基础知识已经非常扎实之后再啃。如果你刚把普通树形DP弄明白建议先把常规树形DP的代码敲熟再来碰DDP否则很容易被矩阵化和树剖两头夹击。5.3 学习路径建议别让优化技巧成为空中楼阁我见过不少朋友一上来就学动态DP结果连普通树上背包都写错。我的个人建议是学习DP的路线应该是先把线性DP、区间DP、树形DP的朴素解法写熟再补状态机、数位DP这类状态定义有花样的模型然后才轮到单调队列、四边形不等式、wqs二分这些优化最后再去碰动态DP这类模型组合的高级玩法。每层都配合能指出这道题考的是哪个模型、哪种优化的自我训练。没有前面几层地基学再炫的优化也是一碰就碎。6. HAO自己踩过的DP坑七个看起来小、实际上能卡一整天的错误最后这部分是纯实战经验。DP题错得最多的往往不是思路而是实现细节。下面七个坑我全都在板子上踩过每一个都至少卡了我两个小时以上。6.1 循环顺序背包为什么必须倒着循环容量滚动数组优化01背包时容量循环要倒序。原因是dp[j] max(dp[j], dp[j - w[i]] v[i])如果正序dp[j - w[i]]可能已经在当前这一轮被更新过相当于同一个物品被使用了多次。倒序则保证每个物品最多被选一次。我建议你想清楚这个过程而不是只记倒序。如果你做的是完全背包那才需要正序。这个“正倒序之争”背后是物品可重用的次数理解了就不会出死记硬背导致的笑话。6.2 INF取值不是越大约好很多人初始化dp用0x7fffffff但转移里有加法两个大的INF一加就溢出变成负值然后 min 的结果完全错误。我在写矩阵连乘这类区间DP时就吃过这个亏。推荐用0x3f3f3f3f约等于 10^9两个相加也不会爆 int而且 memset 对 0x3f3f3f3f 有快速的字节填充方式。如果是 long long 的DP用0x3f3f3f3f3f3f3f3f。6.3 long long 和中间溢出乘法比结果更早爆炸计数类DP里即便答案保证在 int 范围中间状态也可能经过dp[u][j] dp[u][j-k] * dp[v][k]这种组合。乘法过程一旦溢出后面再怎么取模都没用了。判断是否用long long不要只看题目说最终答案取模要看中间乘积会不会超过 2^31。这个习惯我是在LeetCode和牛客上百度和优化题里反复栽跟头之后才彻底养成。6.4 记忆化搜索的缓存冲突0到底代表可行方案还是没有方案数位DP或计数DP里记忆化数组初始化成 -1 表示还没算过这是为了防止方案数恰好为0被当成没算过而反复递归。我犯过的错误初始化数组为 0然后判断if (dp[...] ! 0) return dp[...];结果合法方案数为0的路径永远没法缓存同一个子问题被重复算几千次直接超时。记住要么初始化成 -1要么开一个vis布尔数组单独标记。6.5 单调队列优化队头过期下标要先弹再取最优这个我在 4.1 里强调过但值得再单独拉出来说一次先弹队头过期下标再取队头再往队尾插新元素。三个操作顺序一旦错单调队列守不住窗口边界答案就会混入范围外的状态。新手最容易漏掉第一步拿了个过期状态当最优解调试半天还觉得是方程的问题。6.6 树形DP的递归栈溢出当n到20万时怎么办树形DP如果直接递归在链状树上深度达到 20 万C 默认栈会爆掉。我的处理办法有几种一是手动用stack模拟DFS先序和后序分开处理二是先把树递归改成非递归遍历按进栈顺序记录一个操作序列再逆序做状态合并。在比赛环境下实在不行也可以换编译器参数但我不建议依赖这个。对于面试场景只要你能指出递归在链状树上会栈溢出并说出迭代解法思路面试官往往就满意了。6.7 边界初始化dp[0][0]1和dp[0][0]0之间隔了一场事故计数类DP里求凑成总金额X有多少种方式时dp[0] 1是条件反射。但在从一堆数里选若干个数使和恰好等于X这类01背包计数题里dp[0] 1依然成立然而很多人在循环里把dp[j] dp[j - a[i]]的容量循环写成正序导致同一个数被选了多次。计数DP的初始化和转移顺序是最容易同时踩中6.1和6.4两个坑的地方。老实说我整理HAO的DP这套笔记的初衷就是因为上述这些坑每个都让我痛过一次。把错误记录下来比单纯记录正确模板更有价值。你自己刷DP题时也可以照着这个思路每做错一题就补进一个为什么会错的条目。久而久之你会形成一种直觉看到题目先问状态有哪些维度再看转移有没有优化空间最后在写代码前把循环顺序、INF、缓存初始化这些坑在脑子里提前过一遍。这样下来DP题对你就不再是玄学而是一套有章可循的工程实践了。