动态规划这四个字劝退了多少人我自己就是从被劝退到靠它吃饭过来的。刚开始刷题的时候一看到“动态规划”四个字就头皮发麻什么状态转移方程、子结构、无后效性每一个词听起来都像在说天书。后来刷了上百道题才慢慢摸出门道发现它其实是有固定套路可循的尤其用C写DP模板感非常强状态换一换骨架基本不变。这篇文章我准备把整套思路、判断方法、C模板和调试技巧全部倒出来目标读者是三类人刚接触DP、被状态转移方程吓退的新手会做模板题但遇到变形就发懵的进阶者以及想快速复习DP核心套路准备机试或面试的同学。看完以后你再拿到一道新题至少知道从哪里下手而不是盯着数据范围发呆。1. 动态规划的整体设计与思路拆解1.1 动态规划到底在解决什么问题动态规划Dynamic Programming简称DP本质上就一句话把大问题拆成有重叠关系的子问题先把每个子问题的答案算出来并记下来再用子问题的答案组合出大问题的答案。它跟“递归”最大的区别在于递归是只拆不算而DP是拆完以后把每个小结果都存起来。我用一个生活化的例子解释。爬楼梯每次可以跨1级或2级问到第10级有多少种走法。你要到第10级最后一步要么从第8级跨2级上来要么从第9级跨1级上来。所以第10级的答案一定等于第8级答案加第9级答案。这就是DP公式的雏形当前状态由前面几个状态相加得到。再往深处想这个思路能解决大量看似复杂的问题。比如背包问题容量有限的背包要装哪些物品使总价值最大。如果暴力枚举所有组合2的N次方种方案N稍微大一点就直接爆炸。DP的做法是把“背包容量还剩多少”“已经考虑了前几件物品”作为状态每算出一个子状态就存下来后面的计算直接拿过来用避免重复枚举。所以DP的核心从来不是“怎么写出一个公式”而是“如何把一个大问题拆成若干个小问题并且让这些小问题之间形成清晰的依赖关系”。一旦拆法想明白了代码反而是最简单的部分。1.2 DP成立的三条前提条件不是所有问题都能用DP能用DP的问题必须同时满足三个条件。第一个是最优子结构。意思是整个问题的最优解一定可以由子问题的最优解组合出来。比如背包问题里容量10的最优方案一定是在容量小于10的某个最优方案基础上再决定装不装当前物品。如果这个性质不成立DP算出来的就可能是垃圾答案。第二个是重叠子问题。同一个子问题会被反复使用所以才需要记录。斐波那契数列里 f(7) 会被 f(8) 和 f(9) 反复用到如果纯递归会重复计算无数遍DP就把 f(7) 算一次存起来谁用谁拿。如果没有重叠性比如归并排序每个子问题只出现一次那用DP反而是浪费内存。第三个是无后效性。这是最容易被忽略的一条。意思是某个状态一旦确定后续怎么走只跟当前状态有关跟“我之前是怎么到达这个状态的”无关。比如棋盘上从左上角走到右下角如果题目只允许向右和向下走那么只需要记录当前坐标不需要记录走过的路径但如果题目加了“某些格子不能重复经过”这种限制状态里就必须带上路径集合否则就违反了无后效性DP结果会错。判断一个题能不能DP我一般先看这三条缺一条就换思路。1.3 DP与贪心、递归、分治的本质区别很多新人把DP和递归、贪心、分治混在一起我在这里一次说清楚。贪心的思路是每一步都选当前看起来最好的然后一路走到底从不回头看。DP则不同DP会枚举所有可能的子状态把各种选择都算出来再取最优。比如硬币找零问题硬币面额是1、5、11要找15元贪心会先拿11然后1111一共5枚但最优其实是555只要3枚。贪心在这个问题上栽了DP不会。递归是一种程序写法DP是一种算法思想。DP既可以用递归实现自顶向下加记忆化也可以用循环实现自底向上的递推。所以“递归DP”和“递推DP”说的是实现方式不是两种不同的算法。分治和DP很像都是把大问题拆成子问题但分治要求子问题互不重叠典型就是归并排序、二分查找。DP处理的是重叠子问题。判断标准很直接如果同一个子问题会被重复计算就是DP的地盘如果各子问题彼此独立就用分治。1.4 快速识别一道题该不该用DP我拿到一道新题判断是不是DP通常看三样东西。第一看问法。题目问最大值、最小值、方案数、能不能达到某个目标这四种问法命中DP的概率极高。比如“最大子序和”“最长递增子序列”“有多少种方式凑出金额”“能否分割数组”这些都是DP的信号。第二看数据范围。DP的时间复杂度通常是O(n)、O(n²)或O(n³)。如果n在1000到100000这种量级我第一反应就是往DP想。具体来说n小于等于20可能是状态压缩DPn小于等于100可能是O(n³)区间DPn小于等于5000大概率是O(n²)线性DPn在1e5级别那就需要数据结构优化DP或者贪心加二分。第三看决策的性质。如果后面决策受到前面某些状态影响但这些影响能通过状态里的几个参数完整描述出来那就基本上是DP了。比如打家劫舍当前偷不偷要考虑前一户有没有偷这个信息可以用一个布尔状态存下来那就满足DP条件。2. 动态规划的核心细节与实操要点2.1 打算法草稿DP五步法我带新人写DP一定会让他们先打草稿不要急着写代码。草稿的格式我固定叫“五步法”每次写DP题都按这五步走。第一步定义状态。dp[i]表示什么一维不够就二维二维不够就加维度。这一步相当于写SQL时先确认要查哪张表、取哪些字段。状态定义错了后面全是无用功。第二步写状态转移方程。假设所有比当前状态规模小的状态都已经算好当前状态怎么由它们组合出来。这一步是整个DP的核心也是大多数人卡住的地方。第三步确定初始化和边界条件。dp[0]是0还是1dp[1]怎么设置这些边界错了整个DP表就会从头错到尾。第四步确定计算顺序。从规模小的状态往规模大的状态推写循环时要想清楚外层循环是什么内层循环是什么。第五步确定答案在哪里。答案有时候是dp[n]有时候是某一维的最大值有时候要遍历整个DP数组才能取出答案。我把这五步做成了一张固定检查单每做一道DP题就在草稿纸上完整写一遍。前期看起来浪费时间但坚持一个月之后写DP的速度和准确率会有质的提升。2.2 状态设计不重不漏的关键技巧状态设计最讲究的两个字是“不重不漏”。不重是指不要有多余的信息不漏是指不能缺少关键信息。状态信息过少转移时不够用信息过多维度爆炸内存和复杂度都受不了。我举打家劫舍为例。题目是一排房子偷了相邻两间就会触发报警问能偷到的最大金额。如果只定义dp[i]为前i间房的最高金额那么dp[i]转移时你不知道第i-1间到底偷没偷z干脆没法判断能不能偷第i间。这时候就要加维度dp[i][0]表示前i间房里第i间没偷的最大金额dp[i][1]表示第i间偷了的最大金额。转移就清晰了dp[i][0] max(dp[i-1][0], dp[i-1][1])dp[i][1] dp[i-1][0] nums[i]。再比如路径问题如果题目只允许向右和向下状态只需要行号和列号因为“怎么来到这个格子”不影响下一步。但如果题目说经过的格子不能重复走那状态里就必须带上已经走过的格子集合也就是状态压缩DP的思路。2.3 转移方程怎么想盯住最后一步我教别人写转移方程最喜欢用的方法就是“盯住最后一步”。不管问题多复杂你先把最后一步可能的情况全列出来每种情况对应一个更小的子问题然后把子问题的答案加上最后一步的代价取max、min或者求和方程就出来了。比如最长递增子序列LISdp[i]表示以第i个数字结尾的最长递增子序列长度。盯住最后一步最后一个元素nums[i]要么自己单独成为一个长度为1的子序列要么接在某个nums[j]后面前提是nums[j] nums[i]。所以 dp[i] max(1, dp[j] 1)其中 j小于i且nums[j]小于nums[i]。再比如最长公共子序列LCSdp[i][j]表示字符串A前i个字符和字符串B前j个字符的LCS长度。盯住最后一步比较A[i-1]和B[j-1]如果相等那这个字符一定可以算进LCS里dp[i][j] dp[i-1][j-1] 1如果不相等那就只能继承A少一个字符或B少一个字符时的答案取两者较大值。只要你把“最后一步”想透转移方程基本就是自然流露的结果。反过来如果你一直写不出转移方程很大概率是没想清楚最后一步有哪些可能。2.4 空间优化与遍历顺序的细节DP算完当前层以后很多旧状态再也用不到这时候可以用滚动数组省内存。最典型的例子是斐波那契只需要记录前两个值空间从O(n)压到O(1)。但滚动数组有个必须注意的点循环遍历顺序会影响结果的正确性。01背包的一维优化就是最经典的坑。二维转移方程是dp[i][j] max(dp[i-1][j], dp[i-1][j-w[i]] v[i])压缩成一维以后容量维度必须从大到小遍历。为什么因为一维数组里存的是“上一层”的结果如果从小到大更新dp[j-w[i]]已经被当前物品更新过再拿来用就相当于允许同一件物品反复选从大到小更新时dp[j-w[i]]还没被当前物品碰过取到的还是上一层的值正好对应01背包“每件最多选一次”的语义。完全背包没有这个限制所以内层从w[i]到V正序遍历。我常用一句话记忆01背包从大到小完全背包从小到大方向反了模板就废了。3. C DP模板实战直接能抄的代码3.1 线性DP与滚动数组模板先从最简单的爬楼梯开始。题目每次可以爬1或2级台阶问到第n级有多少种方案。状态定义dp[i]是爬到第i级的方案数转移是dp[i] dp[i-1] dp[i-2]。因为只依赖前两级滚动数组可以直接上场。#include bits/stdc.h using namespace std; int climbStairs(int n) { if (n 2) return n; int prev2 1; // dp[i-2] int prev1 2; // dp[i-1] for (int i 3; i n; i) { int cur prev1 prev2; prev2 prev1; prev1 cur; } return prev1; } int main() { int n; cin n; cout climbStairs(n) endl; return 0; }这个模板可以扩展成“每次能爬k级”的版本只要把转移改成前k个状态的累加即可。做题时有个习惯要养成先检查n小到边界时能不能正确返回比如n等于1和2我每次都会在循环前做一个快速判断防止数组访问越界或者公式出现负下标。3.2 背包DP模板01、完全、多重背包问题几乎是DP的代名词面试和竞赛里出现的频率高得离谱。01背包的二维模板很好理解dp[i][j]表示前i件物品背包容量为j时的最大价值。对于第i件物品要么不装要么装。不装就是dp[i-1][j]装的话要先给这个物品留出w[i]的空间也就是dp[i-1][j-w[i]] v[i]。一维压缩后的C模板我每次写背包题都会直接用重点看内层循环方向int bag01(int N, int V, const vectorint w, const vectorint v) { vectorint dp(V 1, 0); for (int i 0; i N; i) { for (int j V; j w[i]; --j) { // 逆序保证每件物品只用一次 dp[j] max(dp[j], dp[j - w[i]] v[i]); } } return dp[V]; }完全背包的区别只是内层循环变成正序int bagComplete(int N, int V, const vectorint w, const vectorint v) { vectorint dp(V 1, 0); for (int i 0; i N; i) { for (int j w[i]; j V; j) { // 正序允许重复选取 dp[j] max(dp[j], dp[j - w[i]] v[i]); } } return dp[V]; }如果要求“把背包装满”而不是“不超过背包容量”初始化时把dp[0]设成0其余设成负无穷这样只有能从dp[0]合法转移过来的状态才是有效值。还有一个高频变种是“求方案数”转移方程会从max变成累加dp[j] dp[j - w[i]]这时候初始化dp[0]1含义是“凑出0元有一种方案就是什么都不选”。多重背包是每件物品最多有c[i]件最粗暴的办法是把c[i]件拆成c[i]个独立物品跑01背包。但数据一大就会超时得用二进制优化把c[i]拆成1、2、4、...、剩余的组合这样任意数量都能由这些块拼出来复杂度从O(Nc[i])降到O(Nlog c[i])。这算包裹进阶技巧新人先把01背包吃透再上这个。3.3 LIS与LCS模板最长递增子序列的O(n²)写法是最容易理解的。dp[i]表示以nums[i]结尾的LIS长度初始化全是1因为每个数字自身至少是一个长度为1的子序列。转移时需要枚举i之前的所有j满足nums[j] nums[i]时dp[i] max(dp[i], dp[j] 1)。int lengthOfLIS(vectorint nums) { int n nums.size(); vectorint dp(n, 1); int ans 1; for (int i 0; i n; i) { for (int j 0; j i; j) { if (nums[j] nums[i]) { dp[i] max(dp[i], dp[j] 1); } } ans max(ans, dp[i]); } return ans; }当n到达1e5级别O(n²)会超时。此时改用贪心加二分维护一个d数组d[len]表示长度为len的递增子序列的最小末尾值。遍历nums[i]用lower_bound在d中找到第一个大于等于nums[i]的位置替换成nums[i]。这个优化看着绕核心思想是让每个长度的“潜力值”尽量小后续才更容易接上更长的子序列。最长公共子序列是二维DP的地基模板。状态dp[i][j]表示A前i个字符和B前j个字符的LCS长度。字符相等时从dp[i-1][j-1]转移不相等时从dp[i-1][j]和dp[i][j-1]里取较大值。int longestCommonSubsequence(string a, string b) { int n a.size(), m b.size(); vectorvectorint dp(n 1, vectorint(m 1, 0)); for (int i 1; i n; i) { for (int j 1; j m; j) { if (a[i - 1] b[j - 1]) { dp[i][j] dp[i - 1][j - 1] 1; } else { dp[i][j] max(dp[i - 1][j], dp[i][j - 1]); } } } return dp[n][m]; }这里下标从1开始其实是刻意为之dp[0][j]和dp[i][0]天然表示空串的情况值为0省去了大量的if边界判断。我建议新手写DP时尽量用1-based下标转移方程会干净很多。3.4 区间DP模板石子合并区间DP的套路跟线性DP不太一样它的状态通常是二维的dp[l][r]表示闭区间[l, r]上的最优答案。以石子合并为例有n堆石子排成一排每次只能合并相邻两堆合并代价是两堆石子数之和问最小总代价。转移方程是dp[l][r] min(dp[l][k] dp[k1][r] sum(l, r))其中k从l枚举到r-1sum(l, r)是区间内石子的总重量用前缀和O(1)算出来。int stoneMerge(vectorint stones) { int n stones.size(); vectorint prefix(n 1, 0); for (int i 1; i n; i) { prefix[i] prefix[i - 1] stones[i - 1]; } const int INF 1e9; vectorvectorint dp(n 1, vectorint(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] prefix[r] - prefix[l - 1]); } } } return dp[1][n]; }注意循环必须先枚举区间长度再枚举左端点为什么不能直接枚举l和r因为dp[l][r]依赖的是更短的区间如果不按长度从小到大算可能出现dp[l][k]还没算出来就去用了的情况。这也是区间DP最容易写错的地方。还有初始化时长度1的区间本来就不需要合并代价为0所以len从2开始枚举dp[l][r]初始化为INF防止在min时被0污染。3.5 记忆化搜索通用框架有些题目递推形式不好写比如搜索式的问题、带复杂条件转移的问题这时候记忆化搜索就特别香。它的本质是DFS加缓存代码结构固定先写递归函数参数就是状态递归边界处理最小状态查缓存命中就直接返回否则计算并写入缓存。int n; vectorint memo; // 初始化为-1表示还没有计算 int dfs(int i) { if (i 0) return 1; // 递归边界 if (i 1) return 2; if (memo[i] ! -1) return memo[i]; // 剪枝 return memo[i] dfs(i - 1) dfs(i - 2); } int main() { cin n; memo.assign(n 1, -1); cout dfs(n) endl; return 0; }记忆化搜索有三个习惯我每次都会强调。第一个memo初始化值必须选一个状态里不可能出现的值比如这里是-1否则会把真实答案和“未计算”混为一谈。第二个递归边界一定要写在查缓存之前不然边界就永远不会被正确返回。第三个参数多的时候可以用map做记忆化但性能不如数组能用数组索引映射的状态优先用数组。3.6 状态压缩DP模板当题目中某个维度规模极小比如n不超过20我们可以用一个int的二进制位来表示集合。每一位代表一个元素是否在集合里这就是状态压缩。最短Hamilton路径是状态压缩DP最经典的入门题。状态定义dp[mask][i]表示已经访问的城市集合为mask当前位于城市i的最短距离。初始状态dp[1][0]0表示已经从城市0出发mask里只有第0位是1。转移时枚举当前城市i和下一个还没访问的城市j更新dp[mask | (1 j)][j]。int tsp(int n, vectorvectorint dist) { int size 1 n; vectorvectorint dp(size, vectorint(n, 1e9)); dp[1][0] 0; for (int mask 1; mask size; mask) { for (int i 0; i n; i) { if (!(mask (1 i))) continue; for (int j 0; j n; j) { if (mask (1 j)) continue; dp[mask | (1 j)][j] min(dp[mask | (1 j)][j], dp[mask][i] dist[i][j]); } } } return dp[size - 1][0]; }写状态压缩DP时我建议先把每个bit的含义写在注释里比如“第k位表示城市k是否已访问”不然位运算写多了很容易分不清mask到底代表什么。此外n超过20时2^n就会爆炸所以看到这个状态量级要立刻判断是否适用。4. 常见问题与排查技巧实录4.1 定位DP错误的三板斧我在实际刷题中DP出问题了从不直接瞪眼读代码而是用三板斧。第一板斧打印DP表。每算完一行就输出一行关键状态观察从哪一行开始不符合直觉。比如LCS题目中如果dp[2][3]比dp[3][2]还大多半是转移条件写反了或者下标偏移出了问题。第二板斧构造极小样例。n取3或4手工把整个DP过程一步步算出来再用程序输出对比。大多数错误在前几个状态就能暴露不需要跑到大数据才发现。第三板斧写暴力对拍。对小规模n用DFS枚举所有方案求正确答案然后随机生成多组测试数据拿DP结果跟暴力结果比对。这个小程序虽然写起来烦但能把隐藏极深的逻辑错误揪出来而且只要写一次后面同类DP题都能复用。4.2 状态定义有问题的典型症状状态定义错了通常有几种明显症状。第一种是答案差一点点但怎么改都补不上很可能就是“信息不够”。比如打家劫舍只定义了dp[i]没定义第i间房偷没偷答案总是跟正确答案差那么几个数字原因就是状态里缺少了关键信息。第二种是状态之间出现循环依赖。递推计算到某一个状态时它需要的另一个状态还没算出来或者反过来需要它自己。表现就是计算结果跟循环枚举顺序有关换一种遍历顺序答案就变了。遇到这种情况不要试图调循环赶紧重新想状态定义。第三种是状态冗余内存大得离谱。比如明明可以用一维表示的状态非要写二维虽然结果对但复杂度超标。这时候要回头检查是不是状态里塞了不需要的信息。4.3 边界条件与数据溢出的那些坑边界问题是DP翻车的重灾区尤其是数组下标。我自己的经验是能开n1就不要开n能用1-based就不要用0-based。很多转移方程写成dp[i-1]或dp[i-1][j-w[i]]的形式下标为0时会出现负下标访问轻则结果错重则段错误。数据溢出则分两种。第一种是答案本身会很大比如方案数DP答案随n增长很快int根本装不下必须用long long。第二种是初始化INF时取值不合适。我用int型INF取1e9用long long型INF取1e18这样再大再大的合法代价也不至于把这个值戳穿同时两个INF相加也基本不会溢出。这里还有一个细节有些DP题目要求结果取模比如模1e97。这种情况下每一处加法都要取模别只在最后取模因为中间状态就可能溢出或过大取模顺序错一点结果全偏。4.4 滚动数组顺序错乱的排查方法很多人一用滚动数组就翻车最常见就是01背包内层循环的方向搞反。如果发现结果出现了“同一件物品被选多次”的现象内层方向从大到小改成从小到大或者反过来。排查的时候我建议先用二维DP写一版不受优化影响的结果再用一维滚动版跑同一个测试两个结果一对比就能确定是不是顺序问题。另一种情况是滚动数组压了多个维度比如二维DP压成一维但转移里同时用到了本层更新过的值和上一层旧值。解决办法是把依赖关系写清楚哪一个是“旧状态”哪一个是“新状态”在代码里用注释标出来。依赖理清了滚动数组就不再玄学。4.5 DP稳步进阶的练习建议如果让我给一条可执行的练习路线我会推荐按这个顺序刷题每个类别刷够5到10道不求快但求每道题都能把五步法写在纸上。第一步线性DP爬楼梯、打家劫舍、最大子数组和、最长递增子序列。这些题目短小精悍适合建立DP直觉。第二步背包DP01背包、完全背包、目标和、零钱兑换。背包模型复用性强是面试高频。第三步区间DP石子合并、最长回文子序列、矩阵连乘。重点理解区间长度循环。第四步状态压缩DP蒙德里安的梦想、最短Hamilton路径。这一阶段需要较强的位运算基础。第五步树形DP二叉树中的最大路径和、树的直径。树形DP通常出现在大厂面试的两道算法题中。刷题的时候我强烈建议每道题都写下状态定义、转移方程、初始化、遍历顺序、答案位置这五个要素再动笔写代码。很多同学看题解时觉得懂了合上题解又不会写缺的正是这个把思路显式化的过程。最后再说一个我自己的习惯同一道DP题做完以后我会尝试用另一种实现方式再写一遍比如把递推改成记忆化搜索把二维改成滚动数组。这样一道题能榨出三倍的训练效果而且对各个模板之间的转化理解会深很多。动态规划不是背模板的学科但它确实有规律可循。把状态设计的基本功练扎实再配合这套C模板遇到新题你就不会慌反而会有点期待把它拆开看看。