1. 先说清楚动态规划到底是什么我在带新人写C项目的时候发现一个挺普遍的现象大家一听到动态规划四个字就紧张觉得它是算法竞赛里那种高不可攀的东西。其实动态规划本身不是什么玄学它就是用一张表把已经算过的结果存下来避免同一个子问题被反复计算。这句话听起来简单但很多人写了很久代码也没真正领会。拿最经典的斐波那契数列来说。你写递归long long fib(int n) { if (n 1) return n; return fib(n - 1) fib(n - 2); }n45的时候我在自己的机器上跑了一下大概要6秒多。为什么这么慢因为fib(40)会被算好几遍fib(39)会被算更多遍这棵递归树里到处是重复节点。换成动态规划本质就多了一行“如果算过就直接取”long long fib(int n) { vectorlong long dp(n 1, 0); dp[1] 1; for (int i 2; i n; i) { dp[i] dp[i - 1] dp[i - 2]; } return dp[n]; }n45跑出来是0.00002秒级别。同一个问题差距是几十万倍。这就是动态规划最朴素的动机用空间换时间。但我得澄清一件事动态规划不是某一种具体的算法。二分查找是算法冒泡排序是算法但动态规划更像是一套针对最优决策类问题的建模思想。它要求你把原问题拆成若干阶段每个阶段做出一个决策并且把每个阶段的中间结果存下来让后面的阶段直接使用。适合用动态规划的问题通常有两个硬性特征重叠子问题大问题拆成小问题时这些小问题会被反复碰到。如果不存下来就会像斐波那契递归一样爆炸。最优子结构大问题的最优解可以由子问题的最优解推导出来。也就是说你不需要知道“次优解”是什么只要每个子问题都取最优最后拼出来的一定是最优。我见过很多人在这一步就栽了。比如求从起点到终点的最短路径贪心算法每步都选当前最短的边结果走出来的不一定是最优。就是因为路径问题虽然没有“重叠子问题”这个概念时让你觉得不适应但一旦把它想成“到终点的最优解 到某个中间点的最优解 最后一段”最优子结构就出来了DP自然成立。写这篇文章我就是想用做项目的心态把动态规划从头到尾拆开把状态怎么设计、转移方程怎么写、C代码怎么优化、遇到WA怎么排查这些事讲透。不搞悬空的理论每个模型都配代码模板。2. 设计状态与转移方程动规的真正分水岭很多人看动态规划的题解觉得“dp[i] max(dp[i-1], nums[i])”这种式子很简单但真到自己写就卡住。原因很简单你没搞清楚这个式子是怎么来的。2.1 状态设计先回答dp数组里的每个值代表什么状态就是dp数组每一项的含义。一个好状态必须满足两个条件一是有明确的“阶段”概念二是在做决策时它已经囊括了所有需要的信息。判断状态设计得好不好的经验每一个约束条件对应一个维度。拿最长上升子序列LIS来说。题目要求“以nums[i]结尾的最长上升子序列长度”。我为什么要限定“以nums[i]结尾”因为只有知道当前末尾是谁才能判断下一个数能不能接上去。所以状态就是// dp[i]以 nums[i] 结尾的最长上升子序列长度 vectorint dp(n, 1);再拿01背包问题来说。你有N件物品每件有重量w[i]和价值v[i]背包容量为W。这里有两个约束物品编号i、背包容量j。所以状态天然是二维的// dp[i][j]前 i 件物品中选总重量不超过 j能获得的最大价值 vectorvectorint dp(N 1, vectorint(W 1, 0));如果某个决策变量没有进状态转移方程大概率写不出来。这是很常见的新手误区——偷懒把状态设少了结果发现没法转移或者转移时丢信息。反过来也别把无关因素塞进状态。一个经典的错误是求最大子段和时有人把状态设计成“前i个元素的最大子段和”结果发现这个值没法推到i1因为你不知道当前这个子段“断没断”。正确的做法是把状态定义成“以nums[i]结尾的最大子段和”然后在所有dp[i]里取最大值。这就是细节。2.2 转移方程用最后一步反推我写转移方程有一个固定套路假设我现在站在第i个阶段问自己——到达这个阶段上一步是什么还是以LIS为例。dp[i]表示以nums[i]结尾的最长上升子序列长度那我问这个子序列的倒数第二个元素是谁它可能是nums[0]到nums[i-1]之间任意一个比nums[i]小的数。所以dp[i] max(dp[j] 1) // 对所有满足 j i 且 nums[j] nums[i] 的 j这个过程的本质就是把“大问题”拆成“上一步的小问题 最后一步的决策”。写转移方程时我建议你养成一个习惯先在纸上画出“最后一步”的示意图把所有可能的上一步列出来再取max或min。直接上手敲代码大概率敲到一半就会乱。01背包的最后一步更直观第i件物品要么不选要么选。// 不选第 i 件容量还是 j价值继承前 i-1 件的最优值 // 选第 i 件需要腾出 w[i] 的容量价值是 dp[i-1][j-w[i]] v[i] dp[i][j] max(dp[i-1][j], dp[i-1][j-w[i]] v[i]); // 前提 j w[i]这就是“最后一步”思路的威力一旦你确定了dp[i][j]的含义转移方程只是把“最后一步的两种可能性”翻译成代码而已。2.3 边界与初始化90%的新手翻车点状态和转移方程都对但程序输出不对大部分问题出在初始化上。我列几个我实测带新人时最常见的坑LIS的dp数组初始化为0还是1。答案是1因为每个元素自身就是一个长度为1的上升子序列。你初始化为0最后结果会少1。背包问题dp[0][j]0表示前0件物品价值为0。但如果你求的是“恰好装满背包”那dp[0][0]0dp[0][j]-INFj0表示“容量为正却没法装满”的情况不存在。到底用0还是-INF取决于题目问的是“不超过容量”还是“恰好装满”一字之差天壤之别。区间DP的dp[i][i]初始值。比如石子合并dp[i][i]0因为只有一堆石子不需要合并。这个不设对后面算长度2以上的区间时全乱套。数组大小。我建议统一开成n1或W1下标从1开始用。C里vector默认初始化为0省事。但下标0如果也参与转移要格外小心语义。初始化这件事我的经验是写代码之前先把“边界定义”写在注释里。哪怕只有一行// dp[0][j]0 前0件物品价值0 // dp[i][0]0 容量0放不进任何东西一旦注释写清楚很多莫名其妙的WA都能在写代码的瞬间被消灭掉。3. 五类高频DP模型与可直接抄的C模板动态规划题型很多但高频率出现、工作中也经常用到的就四五类。我把它们各自的代码模板、转移思路和适用场景整理出来。3.1 线性DP从最大子段和到LIS优化最大子段和是我在所有DP题里最喜欢用来开讲的因为它短小精悍。题目给定数组nums找连续子数组使和最大。int maxSubArray(vectorint nums) { int n nums.size(); vectorint dp(n); dp[0] nums[0]; int ans dp[0]; for (int i 1; i n; i) { dp[i] max(nums[i], dp[i - 1] nums[i]); ans max(ans, dp[i]); } return ans; }注意这个转移方程的巧劲dp[i-1]如果小于0加上它只会拖累当前值所以直接取nums[i]如果dp[i-1]大于0加上它能让和变大。这其实就是在“继续往后延”和“从当前位置重新开始”之间做决策非常典型。LIS的O(n^2)版本模板int lengthOfLIS(vectorint nums) { int n nums.size(); vectorint dp(n, 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); } } } return *max_element(dp.begin(), dp.end()); }这个模板已经能过很多面试题了。如果数据量到10万级别O(n^2)会超时就要换贪心二分的思路维护一个“当前长度对应的最小末尾值”数组配合lower_bound做替换。但那就是另一套玩法了我建议先把O(n^2)的dp思想吃透再进阶。3.2 背包DP01背包为何要倒序遍历背包问题在你搜动态规划相关内容时几乎永远排在前面因为它是“二维状态压缩成一维”最经典的案例。01背包的二维模板// 01背包N件物品容量W重量weight价值value vectorvectorint dp(N 1, vectorint(W 1, 0)); for (int i 1; i N; i) { for (int j 1; j W; j) { if (j weight[i]) dp[i][j] dp[i - 1][j]; else dp[i][j] max(dp[i - 1][j], dp[i - 1][j - weight[i]] value[i]); } }省空间时可以压缩成一维。压缩的原理是dp[i][j]只依赖dp[i-1][j]和dp[i-1][j-w[i]]也就是上一行的两个值。如果我们用一维数组dp[j]表示“当前容量j下的最大价值”并且j从W往0倒着遍历那么dp[j-w[i]]在更新时其实还是上一行的值没有被当前这一行污染这正好满足转移需求。vectorint dp(W 1, 0); for (int i 1; i N; i) { for (int j W; j weight[i]; --j) { dp[j] max(dp[j], dp[j - weight[i]] value[i]); } }如果j正序遍历会怎样那dp[j-weight[i]]可能已经被当前物品更新过了结果就变成了同一件物品可以重复取多次。这正好是“完全背包”的写法。所以很多人记不清遍历方向时就用这个逻辑去推01背包倒序完全背包正序两者只差一个方向含义天差地别。完全背包for (int i 1; i N; i) { for (int j weight[i]; j W; j) { dp[j] max(dp[j], dp[j - weight[i]] value[i]); } }我把这两个模板贴在一起就是提醒你遍历顺序不是死记硬背的它是从状态转移方程的依赖方向推导出来的。3.3 区间DP先枚举长度再枚举起点区间DP和前面几个模型最大的不同是阶段划分不是“第几个元素”而是“区间长度”。典型题目是石子合并有N堆石子排成一排每次只能合并相邻两堆代价是两堆的重量之和求合并成一堆的最小总代价。状态设计// dp[i][j]把第 i 堆到第 j 堆合并成一堆的最小代价 vectorvectorint dp(N 1, vectorint(N 1, INF)); for (int i 1; i N; i) dp[i][i] 0;核心转移最后一步一定是把某个区间[i][k]和[k1][j]两堆合并所以枚举分割点kfor (int len 2; len N; len) { for (int i 1; i len - 1 N; i) { int j i len - 1; for (int k i; k j; k) { dp[i][j] min(dp[i][j], dp[i][k] dp[k 1][j] sum[i][j]); } } }其中sum[i][j]可以用前缀和O(1)求出。区间DP的三重循环顺序几乎都是固定的先枚举长度再枚举起点最后枚举分割点。为什么长度一定要在最外层因为dp[i][j]依赖的两个子区间[i][k]和[k1][j]长度都比当前区间短只有按长度从小到大算才能保证用到的子状态已经算好。这个顺序问题我在带新人时反复强调过。如果写成了“先枚举i再枚举j”很可能在算dp[1][3]的时候dp[2][3]还是INF。3.4 树形DP递归的天然舞台树形DP是动态规划里最“像数据结构题”的一类。题目经典代表是“没有上司的舞会”每个员工有快乐值不能同时选择某个员工和他的直接上司求最大快乐值。树结构天然适合递归所以树形DP通常直接在每个节点上做决策。vectorvectorint tree; // 邻接表 vectorint val; // 快乐值 vectorvectorint dp; // dp[u][0]:不选u, dp[u][1]:选u void dfs(int u, int parent) { dp[u][1] val[u]; for (int v : tree[u]) { if (v parent) continue; dfs(v, u); // 不选 u子节点可选可不选 dp[u][0] max(dp[v][0], dp[v][1]); // 选 u子节点只能不选 dp[u][1] dp[v][0]; } }这个模型的实际用处远不止题库。我在做游戏开发相关项目时用树形DP处理过“技能树加点最优方案”的简化问题。游戏里技能是一棵树学某个技能需要先学父技能每个技能点有收益点数有限怎么分配收益最大——本质上就是一棵树上的分组背包套层树形DP就能算。树形DP的核心心法是“自底向上”子节点算完父节点才能算。所以dfs里先递归子节点再累加结果。这也提醒你树形DP需要正确构建邻接表别在深搜时忘记把父节点传进去不然会死循环。3.5 状态压缩DP当集合本身成为状态状态压缩DP的高频场景是“集合上的最优决策”比如旅行商问题从起点出发走完所有城市再回来求最短路径。此时“当前去过哪些城市”是状态的一部分没法用简单的i或j表示于是用二进制位表示集合// dp[mask][i]已经访问城市集合为 mask最后停留在城市 i 的最短路径 vectorvectorint dp(1 n, vectorint(n, INF)); dp[1 0][0] 0; // 从城市0出发 for (int mask 0; mask (1 n); mask) { for (int i 0; i n; i) { if (!(mask (1 i))) continue; // i 不在集合里 for (int j 0; j n; j) { if (mask (1 j)) continue; // j 已在集合里 dp[mask | (1 j)][j] min( dp[mask | (1 j)][j], dp[mask][i] dist[i][j] ); } } }n超过20这种写法就不太行了因为(1n)的状态数在n20就是上百万再乘n的复杂度会爆。但作为理解“状态压缩”思想的入门这个模板非常清晰。它最大的启发是当你发现所有常规维度都无法完整表达状态时把“是否包含某个元素”这个集合本身作为一个维度。4. C实现DP的三个性能优化细节上面的模板能让你AC大部分题目但C写动态规划要想追求极致性能还有几个细节值得抠。4.1 滚动数组内存减半逻辑不变二维DP中如果dp[i]只依赖dp[i-1]就可以用两个一维数组交替使用或者用偏移量取模。拿LCS最长公共子序列来说vectorvectorint dp(m 1, vectorint(n 1, 0)); for (int i 1; i m; i) { for (int j 1; j n; j) { if (s1[i-1] s2[j-1]) dp[i][j] dp[i-1][j-1] 1; else dp[i][j] max(dp[i-1][j], dp[i][j-1]); } }这里dp[i][j]只依赖上一行的dp[i-1][j-1]、dp[i-1][j]和当前行的dp[i][j-1]。于是可以用两个一维数组vectorint prev(n 1, 0), cur(n 1, 0); for (int i 1; i m; i) { for (int j 1; j n; j) { if (s1[i-1] s2[j-1]) cur[j] prev[j-1] 1; else cur[j] max(prev[j], cur[j-1]); } swap(prev, cur); fill(cur.begin(), cur.end(), 0); // 新一轮清零 }注意这里有个容易踩的坑cur[j]在进入新一行之前必须清零或者你在每次循环内对j0手动赋值。否则上一轮残留数据会污染本轮结果。我已经数不清见过多少次因为忘记清空cur而导致的诡异WA。4.2 记忆化搜索自顶向下也能AC虽然动态规划大部分时候写成自底向上的递推但有一类问题用自顶向下的记忆化搜索更好写状态转移顺序不直观或者状态本身是二维以上的复杂结构。最经典的例子是“滑雪”给定二维矩阵每个点高度不同只能从高处滑向相邻低处求最长滑行长度。int dx[4] {1, -1, 0, 0}; int dy[4] {0, 0, 1, -1}; vectorvectorint memo(n, vectorint(m, -1)); int dfs(int x, int y, vectorvectorint grid) { if (memo[x][y] ! -1) return memo[x][y]; int best 1; for (int d 0; d 4; d) { int nx x dx[d], ny y dy[d]; if (nx 0 nx n ny 0 ny m grid[nx][ny] grid[x][y]) { best max(best, dfs(nx, ny, grid) 1); } } return memo[x][y] best; }记忆化搜索的好处是代码结构和暴搜几乎一样只是在进入子问题前先查表在返回时写表。对新手来说自顶向下的思维负担小很多。它的缺点是函数递归有栈开销状态特别多时不如递推快但在实际题目中作为“能AC”的方案完全合格。我的建议是如果你能很快写出递推就写递推如果一时想不清遍历顺序先写记忆化搜索至少能拿到大部分分数然后逐步改成递推。4.3 少引入不必要的新维度写DP时有一个常见倾向觉得维度越多越好什么状态都往dp数组里塞。其实状态维度越高时间和空间复杂度都指数上升。我见过有人把本来一维能解决的问题硬写成二维比如最大子段和非要搞一个dp[i][0/1]表示是否选第i个最后一个max搞半天。能用一维就用一维。另外C里vectorvector 的连续访问性能不如一维数组因为每行可能不连续。追求极致性能时可以开一个一维数组手动算下标vectorint dp((n 1) * (m 1), 0); auto get [](int i, int j) { return dp[i * (m 1) j]; };但这个写法可读性较差我建议日常开发优先保证可读性只有明显性能瓶颈时才这样做。5. 从WA到ACDP调试的完整思路再熟练的工程师写DP也会WA这不丢人。丢人的是拿到WA后不知道怎么排查。我把自己常用的DP调试流程完整写出来。5.1 第一步小数据手工模拟数据量小的时候直接在草稿纸上手算一遍dp表看跟自己程序输出对不对得上。以LCS为例s1abcs2ac我手算dp表ac000a011b011c012答案应该是2。如果程序输出是1说明转移时相等分支没走对或者数组下标从1开始时的映射写错了。手工模拟对大一点的数据不现实但它能帮你确认“算法思路本身有没有问题”。如果手算都对程序输出错问题一定在代码细节——下标偏移、初始化、循环边界。5.2 第二步在关键位置打印dp表调试动态规划最直接的办法就是把dp表打出来。不要觉得打印日志低级它比任何调试器都好用因为你要看的是“整张表的演进过程”。// 每算完一行就打印 for (int j 0; j n; j) { printf(%d , cur[j]); } printf(\n);打印出来之后重点盯三件事第一行的初始值是不是你预期的边界值。从第二行开始每个格子的值是不是“基于上一行算出来的”。有没有哪一行突然变成0或极大值如果有大概率是数组没清空或者下标越界。下标越界是C里最恶心的DP bug。vector用越界下标时行为未定义可能在某个角落默默改坏别的内存导致结果时对时错。我强烈建议Debug模式下开启AddressSanitizer或至少多用at()访问来定位越界// 调试时用 at()越界会抛异常 dp[i][j] dp[i - 1].at(j - weight[i]) value[i];5.3 第三步三类反复出现的bug清单我整理了一个高频bug对照表每次WA排查时对着过一遍基本能覆盖90%的情况。症状可能原因修复方向答案比预期小dp初始化值错误如LIS初始为0检查每个状态的最小合法值答案比预期大转移时用了还没更新的状态检查遍历顺序是否满足依赖方向结果始终是0循环没进或状态根本没转移检查循环边界和if条件小数据对大数据错数据类型溢出或下标越界导致内存被污染改用long long开启sanitizer检查答案差异没有规律滚动数组没重置检查每轮使用前是否清零这里面数据溢出是我特别想提醒的。C的int在绝大多数评测环境是32位最大值21亿出头。动态规划里涉及“最大价值”“路径总数”这类问题很容易在中间计算时超过这个值。我在刷题时养成一个习惯凡是涉及加法、乘法的DP状态值一律用long long防止AC变WA。5.4 第四步暴力和DP对拍我强烈推荐如果你手头有暴力算法DFS或穷举可以求出正确答案那调试效率最高的是把它写成对拍程序。随机生成小规模数据分别跑暴力解和DP解不一致就停下来打印数据。// 伪代码思路 while (true) { generate_test_data(); int ans1 brute_force(); int ans2 dp_solution(); if (ans1 ! ans2) { print_data(); break; } }这个方法在ACM圈子里是标配但很多刚开始做算法题的人不知道。它的核心价值在于随机数据能覆盖掉你手工模拟时想不到的边界场景。比如全是0、全是负数、元素全相等、容量刚好等于物品总重量——这些极端情况手工很难想全随机对拍能在几秒内帮你测出来。写在最后我的一些实在经验动态规划这名字听起来高级骨子里就是“聪明的穷举结果复用”。我见过两种极端的人一种觉得它难一种觉得它简单但写代码时全看运气。真正靠谱的学习路径是把每个模型的“状态设计、转移方程、遍历顺序”三件事想明白再慢慢形成条件反射。我个人有几个经验顺手分享给你。第一新DP题的调试时间如果超过30分钟果断重写一遍。很多时候重写比找bug快因为重写时你会更谨慎很多低级错误在重写过程中自然就消失了。第二所有状态转移先写注释再写代码把“dp[?]表示什么”写在对应行上面。这个方法土但我在带人的时候发现它真的能显著降低出错率。第三每个模板尽量亲手敲一遍别复制。敲的过程中你会注意到很多细节比如循环边界、等号是否取到这些往往是WA的根源。动态规划是那种“做多了会上瘾”的东西。当你真正理解状态如何设计、转移如何推导之后再看到一道新题脑子里滑过的第一个念头不再是“我不会”而是“我先想想它最后一步是什么”那种感觉是很爽的。希望这篇东西能帮你找到那个进入状态的路口。