拿到一道动态规划的题最痛苦的不是写代码而是根本不知道从哪下手。状态怎么定义为什么要这么转移初始化为什么是 0 和 INF 而不是别的数这些卡点我当年学的时候全都经历过。网上讲动态规划的文章不少但大多要么堆概念要么直接上题解看完还是一头雾水。我写这篇的思路很明确把动态规划从“看到题→想出状态→推出方程→写出 C 代码”这条链路完整走一遍给你一套能直接套用的思维模板再配合代码模板让你以后再见到这类题心里有个清晰的底。这篇文章适合正在准备算法面试的开发者、参加 OJ/竞赛的学生也适合自学数据结构与算法、卡在动态规划这道坎上的朋友。我会尽量用大白话把原理讲透再用 C 把模板写出来你拿过去就能用。1. 先分清能做的和不能做的题型DP 的识别信号与排除法很多人一看到“求最值”“求方案数”就条件反射觉得是 DP结果做半天发现根本推不出状态转移。这里有一个非常关键的认知误区动态规划不是所有最优问题都能解它的成立有严格前提。1.1 动态规划成立的两个硬性前提第一个前提叫最优子结构。大白话就是整个问题的最优解可以由子问题的最优解拼出来。这就像期末复习你打算在三天内让总分最高如果每天只能复习一科那最后一天选哪科取决于前两天复习完剩下的科目后哪科提分空间最大。整体最优由局部最优递推出来这就叫最优子结构。第二个前提叫重叠子问题。如果每个子问题都是全新的答案之间没有任何复用价值那 DP 就没意义。比如归并排序每次划分出来的区间都不一样子问题几乎不重叠用 DP 表去存反而浪费内存。实际上动态规划能比暴力快核心就在于“把已经算过的结果存下来重复使用”。这两个前提在题目里的典型表现是题目明确要求“最大/最小/方案总数”而且你在草稿纸上从最后一步往前推时会发现“前 N-1 步的某类结果”被反复用到。1.2 识别 DP 题的几个信号以及什么时候要主动放弃我刷题的时候会先问自己三个问题能快速排除掉一批“伪 DP”题这个决策是不是只依赖前一个状态如果是而且不形成环大概率是 DP。每一步的选择会不会受更早步骤的“后效性”影响比如状态里只保留当前阶段的某个值就够不需要回溯前两步完整路径这就是无后效性。像求最短路里的“路径具体经过哪些点”就带后效性不能用简单 DP 硬套。直接搜会不会爆炸如果暴力枚举是 2^n 或者 n! 级别而题目数据范围在 10^5 左右基本可以确定要用 DP 或者贪心优化。有一个反直觉的经验要分享下如果题目里每一步的选择和之前的选择强相关导致必须记录完整路径那多半不是 DP 题而是搜索/回溯题的范畴。比如求“从起点到终点的所有路径”虽然也是递推能算的但真正输出路径时你需要额外维护前驱节点数组这已经属于 DP 加路径还原的进阶技巧了。1.3 把 DP 的题型地图先在脑子里建起来我习惯把 DP 题分成几大族见到题目先归个类状态设计的思路会清晰很多家族特征常见题例子核心状态维度线性 DP按顺序处理元素i 从 0 到 n最大子数组和、打家劫舍、最长递增子序列一维或二维背包 DP有容量限制的选择问题01 背包、完全背包、分组背包i物品 j容量区间 DP合并相邻元素求最优石子合并、矩阵链乘、回文串分割i左端点 j右端点树形 DP依赖父子关系的选择树的最大独立集、打家劫舍 III节点 状态位状态压缩 DP集合被压缩成二进制整数旅行商问题、铺砖块mask 位运算这张表是帮我快速定“状态维度”的。如果你能做题时先在脑子里过一遍这个表就不会出现“上来就不知道数组开几维”的尴尬了。2. 状态定义和转移方程的诞生过程从直觉到模板的关键一跃很多教材一上来就甩状态定义仿佛那是从天上掉下来的。实际上状态设计是有方法论的我自己总结了一个思考链条按照这个链条走能搞定八成常规 DP 题。2.1 状态设计的三步提问法拿到题以后不要先想“状态转移方程怎么写”先做这几步把题目要求的结果用一句话写下来。比如“最多能偷到的金额”“最长递增子序列的长度”“凑到 amount 的最少硬币数”。问自己为了得到这个结果我需要知道哪些阶段性的信息这些“阶段性信息”就是状态的参数。比如打家劫舍里关键在于“当前偷到第几家”以及“上一家偷了没偷”。后者可以用一维数组存两种状态也可以直接把“偷/不偷”编进第二维。让状态的维度尽量小。能一维就不二维能二维就不三维。每多加一维时间复杂度和空间复杂度都上一个大台阶。如果发现一维状态推不出来再往二维想这是很正常的过程。2.2 “最后一步”思维写转移方程的万能钥匙状态定义清楚了转移方程怎么出我的习惯是盯着当前状态问自己——如果这是最终答案的最后一步那么上一步有哪些可能用“打家劫舍”这个最经典的例子讲解。题目是一排房子不能偷相邻两家问最大可偷金额。设 dp[i] 表示“偷前 i 间房子能得到的最大金额”然后考虑第 i 间房子不偷第 i 间那么前 i-1 间怎么偷都行dp[i] dp[i-1]。偷第 i 间那第 i-1 间绝对不能偷收益是第 i 间的钱 nums[i] 加上前 i-2 间的最优结果dp[i] dp[i-2] nums[i]。两者取最大就是答案。你看整个过程根本没有“硬想”只是把最后一步的所有可能性枚举出来然后取最优。这个思路几乎能解决所有线性 DP。做最长递增子序列时也是同理以 nums[i] 结尾作为最后一步上一步是“所有值比 nums[i] 小的 nums[j]j i”结尾的子序列。2.3 初始化为什么不是 0 就是 INF边界条件的本质初始化是新手最容易崩的地方。我当年就犯过把“最大”问题初始化为 0导致全负数数组直接算出 0 的错。这里有个通行的判断逻辑如果求的是最大值而且数值可能为负dp 数组初始化为负无穷比如 -1e9保证任何从真实状态转移来的结果都能覆盖初值。如果求的是最小值初始化为正无穷1e9 或 0x3f3f3f3f。如果求的是方案数边界状态初始化为 1其他为 0。如果 dp[0] 有明确的物理意义比如“前 0 个物品的最大价值自然是 0”就直接赋值 0。“0x3f3f3f3f”这个 C 里常用的正无穷常量有个好处它大概等于 10 亿多一点两个这样的数相加不会溢出 int而真正的 INT_MAX 相加会溢出所以写 INF 0x3f3f3f3f 比用 INT_MAX 更安全。2.4 计算顺序为什么大多数是正着循环区间 DP 却要按长度来状态定义好了方程也有了还有一个容易被忽略的点计算顺序必须保证当前状态依赖的子状态已经算完。线性 DP 一般从前往后循环就行因为 dp[i] 依赖的一定是 dp[i-1]、dp[i-2] 这类“更小下标”的状态正序天然满足依赖。但区间 DP 就不一样了。比如 dp[i][j] 表示合并第 i 堆到第 j 堆石子的最小代价它的转移依赖于 dp[i][k] 和 dp[k1][j]其中 k 在 i 和 j 之间。如果你按 i 从小到大循环会出现“dp[i][j] 还没算但后面某个大区间已经想用它”的情况。所以区间 DP 的惯用写法是外层枚举区间长度 len内层枚举左端点 i然后计算右端点 j i len - 1。这样所有短区间都先算完长区间直接取用不会出现依赖未完成的状态。3. 一套 C 模板框架走天下线性、背包与区间 DP 的统一写法状态设计和转移方程这关过了代码其实非常机械。我把自己常用的模板整理如下你可以直接背下来再根据题目微调。3.1 线性 DP 模板一维与二维的基础写法一维线性 DP 最典型的骨架#include bits/stdc.h using namespace std; // 以打家劫舍为例 int rob(vectorint nums) { int n nums.size(); if (n 0) return 0; if (n 1) return nums[0]; vectorint dp(n, 0); dp[0] nums[0]; dp[1] max(nums[0], nums[1]); for (int i 2; i n; i) { dp[i] max(dp[i - 1], dp[i - 2] nums[i]); } return dp[n - 1]; }这里几个细节值得注意dp[1] 为什么是 max(nums[0], nums[1])因为前两个房子不能同时偷所以最优解只能二选一。这种“边界前两三个状态需要单独赋值”的情况在 DP 题里非常常见千万别在循环里从 i0 开始直接套转移方程会越界或者语义错误。二维线性 DP 的模板以“最长公共子序列”为例dp[i][j] 表示 A 的前 i 个字符和 B 的前 j 个字符的最长公共子序列长度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]; }二维 DP 我习惯把 i 和 j 从 1 开始遍历下标 0 那一整行和整列留作边界这样能省去大量if (i 0 j 0)的判断代码干净很多。3.2 背包问题模板01 背包与完全背包的循环方向差异背包问题是 DP 里最需要“背模板”的题型之一但它背后的道理挺简单。01 背包每个物品只能选一次。设 dp[j] 表示容量为 j 的背包能装下的最大价值。int knapsack01(vectorint weight, vectorint value, int capacity) { int n weight.size(); vectorint dp(capacity 1, 0); for (int i 0; i n; i) { // 注意倒序遍历容量 for (int j capacity; j weight[i]; j--) { dp[j] max(dp[j], dp[j - weight[i]] value[i]); } } return dp[capacity]; }为什么容量要倒序遍历因为如果正序遍历dp[j - weight[i]] 可能已经在本轮 i 更新过了那就会变成“同一件物品被装多次”恰好是完全背包想要的效果。所以 01 背包倒序、完全背包正序这个区别是很多面试官喜欢问的点其实原理就这么朴素。完全背包模板只需要把上面内层循环改成正序for (int i 0; i n; i) { for (int j weight[i]; j capacity; j) { dp[j] max(dp[j], dp[j - weight[i]] value[i]); } }3.3 区间 DP 模板按长度枚举是灵魂以石子合并为例dp[i][j] 表示把第 i 堆到第 j 堆石子合并成一堆的最小代价int mergeStones(vectorint stones) { int n stones.size(); if (n 0) return 0; vectorint prefix(n 1, 0); for (int i 1; i n; i) { prefix[i] prefix[i - 1] stones[i - 1]; } vectorvectorint dp(n 1, vectorint(n 1, 0)); // len 表示区间长度从 2 开始长度为 1 时不需合并代价为 0 for (int len 2; len n; len) { for (int i 1; i len - 1 n; i) { int j i len - 1; dp[i][j] INT_MAX; for (int k i; k j; k) { dp[i][j] min(dp[i][j], dp[i][k] dp[k 1][j] prefix[j] - prefix[i - 1]); } } } return dp[1][n]; }区间 DP 的核心就一句话大区间由两个小区间拼起来代价是合并两堆的体力这里用前缀和快速求出区间和。前缀和数组必须提前预处理否则每次计算区间和都要 O(n)整体复杂度直接上一个量级。3.4 树形 DP 模板父子状态的递归转移树形 DP 通常配合 DFS 后序遍历实现。经典例子“打家劫舍 III”二叉树结构不能同时偷父子节点求最大金额。struct TreeNode { int val; TreeNode *left, *right; }; // 返回 [不偷当前节点最大收益, 偷当前节点最大收益] pairint, int dfs(TreeNode* root) { if (!root) return {0, 0}; auto left dfs(root-left); auto right dfs(root-right); int notRob max(left.first, left.second) max(right.first, right.second); int rob root-val left.first right.first; return {notRob, rob}; } int rob(TreeNode* root) { auto res dfs(root); return max(res.first, res.second); }这个模板的精髓在于每个节点返回两个状态值父节点只要看子节点的两个值就能做决策完全不需要额外的记忆化数组。树形 DP 写起来最像递归题但本质上依然是“状态 转移”。4. 空间优化从二维数组到滚动数组再到原地覆盖很多初学者会困惑网上那些题解为什么 dp 是一维的是不是做了不同的状态定义其实大部分情况是空间优化后的结果。理解这个过程对彻底吃透 DP 非常有帮助。4.1 滚动数组把 O(n^2) 压到 O(n)先看一个最简单的场景。斐波那契数列的递推是 f(n) f(n-1) f(n-2)理论上你可以开一个一维数组存下所有值但如果只需要最后一个结果那后边算出来的值直接把前面不用了的覆盖掉就行这就是“滚动数组”的思想。在二维 DP 里如果第 i 行的状态只依赖第 i-1 行完全不需要保留更早的行那么数组可以从dp[n][m]压成dp[2][m]vectorvectorint dp(2, vectorint(m 1, 0)); for (int i 1; i n; i) { int cur i % 2, prev (i - 1) % 2; for (int j 1; j m; j) { // 使用 dp[prev][...] 计算 dp[cur][...] } }用 i % 2 而不是写死 0 和 1是为了让代码能泛化到任意多行的场景。这里的开销很小但压缩效果非常显著。4.2 背包问题为什么可以直接降成一维再回到 01 背包的代码。二维写法是dp[i][j] max(dp[i-1][j], dp[i-1][j-w[i]] v[i])。你会发现第 i 行只由第 i-1 行推出所以优化成一维后dp[j]在更新前保存的其实是“上一轮 i-1 的 dp[j]”。如果正序遍历 jdp[j-w[i]]可能已经被当前物品更新过再拿去用就相当于重复装入同一物品了。只有倒序遍历dp[j-w[i]]才确保是上一轮的旧值正好符合 01 背包“每个物品至多选一次”的语义。这就是为什么很多人背了“01 背包倒序、完全背包正序”却总记反的原因——你只要理解了它在防止什么就永远不会忘。4.3 空间优化的边界检查什么情况下不能强行降维空间优化看起来很美但有一个大坑当转移不仅依赖上一行还依赖更早的行时一维滚动就直接崩了。比如某些状态定义里dp[i][j]依赖dp[i-2][j]如果你只保留上一行数据早就被覆盖掉了。这时候要么回到二维要么用两个一维数组交替存储。还有一个容易踩的坑降到一维后如果你想做“路径还原”也就是不仅要最大价值还要知道选了哪些物品那么必须把完整的二维表存下来。因为一维数组覆盖了历史选项还原时就拿不到足够信息了。我实际写题时经常遇到这种情况所以会提醒自己空间优化别上头先保证功能正确再考虑省内存。5. 从暴力到记忆化再到递推看清 DP 的本质很多教程直接给你 DP 公式导致你只会套模板遇到灵活题就懵。其实动态规划不是凭空出现的它是暴力搜索的“升级版”。理解这条进化链能让你面对新题时心里更有底气。5.1 暴力递归为什么会慢以“凑零钱”为例假设你有一堆不同面值的硬币要凑出 amount 元每种硬币可以用无限次求最少硬币数。最直观的做法是递归f(amount) min(f(amount - coin) 1)对所有 coin 遍历。这样会生成一棵巨大的递归树因为f(10)可能要分别算f(9)、f(8)、f(5)而这些调用的子树又有大量重叠重复计算量呈指数级爆炸。5.2 记忆化搜索加一个缓存就行优化的第一步很简单把已经算过的 f(x) 存下来下次用到直接返回。int dfs(vectorint coins, int amount, vectorint memo) { if (amount 0) return 0; if (amount 0) return -1; if (memo[amount] ! 0) return memo[amount]; int res INT_MAX; for (int coin : coins) { int sub dfs(coins, amount - coin, memo); if (sub ! -1) res min(res, sub 1); } memo[amount] (res INT_MAX ? -1 : res); return memo[amount]; }记忆化搜索本质上已经是一种 DP只不过它是“自顶向下”的递归形式。你觉得递归难理解时可以先写记忆化版本跑对了以后再翻译成递推这对新手非常友好。5.3 从记忆化到双层循环递推把递归改成递推后int coinChange(vectorint coins, int amount) { vectorint dp(amount 1, 0x3f3f3f3f); dp[0] 0; for (int i 1; i amount; i) { for (int coin : coins) { if (i coin) { dp[i] min(dp[i], dp[i - coin] 1); } } } return dp[amount] 0x3f3f3f3f ? -1 : dp[amount]; }这个例子还能很直观地看出完全背包和线性 DP 的统一性dp[i] 只依赖 i-coin 这个更小的状态coin 是外层可枚举的“物品”本质就是完全背包的一维正序写法。当你把各种类型的 DP 都还原为“从暴力到缓存到递推”这个过程后会发现它们在底层是同一件事。6. 实战排错初始化、循环边界和整数溢出最后分享一些我在实际写题中踩过、也帮别人定位过的坑。这些问题在 OJ 上报错往往不直观但你只要掌握规律一眼就能找到病根。6.1 初始化错误最大问题的初始值不是 0我见过最多的错误是把求最大值的 dp 数组全部初始化为 0然后对全负数数组照样跑出 0。比如求“最大子数组和”时如果数组都是负数正确结果是最大的那个负数而不是 0。解决办法很简单dp[0] 或答案变量直接初始化为 nums[0]或者用负无穷初始化后再转移。6.2 循环下标越界/边界状态缺失写数组类 DP 时最容易出问题的是i-1、i-2这类下标。比如打家劫舍里 dp[1] 不初始化就进循环直接越界。我的习惯是写完后先人工跑一遍长度为 0、1、2 的极端样例三个样例全过再提交省得在 OJ 上反复试错。6.3 整数溢出INF 与加法顺序在求值的 DP 里dp[i][k] dp[k1][j] cost三个数相加很容易溢出 int尤其是当 dp 存的是极大值0x3f3f3f3f时再加一个正数就直接变成奇怪的小负数。解决方案有两个一是把 dp 的类型改成 long long二是在相加前判断 dp[i][k] 或 dp[k1][j] 是否已经等于 INF如果是就跳过这个转移。我个人做题时偏向直接用 long long省心回头发草稿再优化精度也来得及。6.4 状态设计不对导致“推出来是错的但不报错”这类问题最隐蔽。程序不崩样例全过提交却 WA。最常见的场景是无后效性被破坏了。举个例子如果状态里只存“当前节点能跳多远”但你转移时偷偷用了“上一次是从哪跳过来的”这个信息那方程看着合理实际却藏了一个隐形依赖小数据没问题数据一大就错。遇到这种情况我建议回到 2.2 节的“最后一步”提问法把所有可能性重新枚举一遍多数时候能发现状态里缺了一维。7. 训练路线从零到竞赛/面试水平的节奏建议动态规划光看不练等于白学。但盲目乱刷效率太低了我建议按下面的路线阶梯式推进。7.1 第一阶段线性 DP 入门1-2 周先刷爬楼梯、最大子数组和、打家劫舍、最长递增子序列、最长公共子序列。这个阶段的目标不是记住代码而是练熟“最后一步推导”的思维。我强烈建议每道题自己先在纸上写出状态定义、转移方程和边界条件再动手敲代码写不出来也没关系但要先想。7.2 第二阶段背包问题专项1 周背包是面试和国际竞赛的高频考点种类多但套路固定。先做 01 背包、完全背包然后是多维费用背包、分组背包。务必自己推一遍“01 背包为什么倒序、完全背包为什么正序”这个理解了背包这一族几乎就拿下了。7.3 第三阶段区间 DP 与树形 DP2 周区间 DP 刷石子合并、矩阵链乘、最长回文子序列树形 DP 刷二叉树最大路径和、树的直径、打家劫舍 III。这个阶段你会发现只要掌握了“按长度枚举区间”和“后序遍历 多状态返回”这两个套路题目之间的差别真的不大。7.4 第四阶段进阶与综合长期状态压缩 DP、数位 DP、概率 DP 都属于进阶内容。如果目标是算法竞赛建议学状态压缩 DP 里最常见的 TSP 问题如果目标是面试可以先放一放反而建议把前面几个 DP 类型的题目做到脑子里能立刻浮现出状态定义和转移方程的程度。训练时我还有一个习惯每做完一道题在代码注释里写一行“这题的状态是什么、为什么这样定义、转移想表达什么”。过两周翻出来看时这行注释比任何题解都管用因为那是你当时的真实思考路径。动态规划这个专题说到底是“带着逻辑地暴力”把所有可能枚举出来用缓存避免重复计算再用状态把问题拆小。每个人都会经历“面对题目大脑空白”的阶段这不是智商问题只是还没建立起状态设计的直觉。按照这篇文章的思路反复练上两周再回头看那些曾经把你卡住的题你会发现自己已经能自然地问出“当前状态依赖哪些子状态”这种问题了。