标题“动态规划十式”这个说法我觉得挺贴切尤其是拿降龙十八掌来类比。动态规划在算法领域的地位说一句“武林绝学”真不夸张——大厂笔试爱考算法竞赛必考就连日常写业务代码偶尔也会蹦出个优化需求逼着你用上它。但很多人一开始看到“状态转移方程”这几个字就懵了觉得这东西太抽象、太难上手。其实动态规划不是靠天赋而是靠套路。我在刷题和带新人的过程中慢慢发现看起来五花八门的DP题翻来覆去就那么十几类板子。你只要把每类的题目特征、状态定义方式、转移方程的写法记清楚再配合足够的训练量考场上遇到DP题基本能稳定拿分。所以这篇文章我想把这几年积累的DP套路整理成“十式”从最简单的线性DP一直讲到状态压缩、树形DP和各类优化技巧每式配一个经典例题再额外补一个完整的最少硬币问题实战流程帮你在脑内建立一套可以反复调用的解题框架。1. 动态规划到底是什么先破解三个底层概念想学招式先得明白内功心法。很多人学DP失败是因为连最基础的概念都模模糊糊直接从题目开始结果越学越乱。所以这一节我先把动态规划的底层逻辑撕开讲清楚。1.1 动态规划解决的问题重叠子问题和最优子结构动态规划最擅长解决的是“最优化问题”和“计数问题”——比如最大收益、最少次数、方案总数。这类问题有一个共同特征大问题的解可以由小问题的解推导出来而且这些小问题会被反复计算。这背后涉及两个关键性质。第一个叫最优子结构意思是原问题的最优解包含了子问题的最优解我一般跟别人解释就是“你每一步都选当前阶段的最优最后拼起来就是全局最优”。第二个叫重叠子问题指的是不同的决策路径会碰到同一个子问题。举个例子你在爬一节一节楼梯时不管之前是走1步还是2步上来的到达第5层之后再往上走的方案数都一样。这个“第5层以后的方案”就被反复用到了。如果一个问题同时具备这两个性质那它大概率可以用DP解决。如果只有最优子结构、没有重叠子问题那用贪心或者分治法更合适如果有重叠子问题但不要求最优那可能是纯计数问题DP依然是好选择。1.2 状态、转移方程、边界条件三件套缺一不可动态规划的代码模板其实特别固定永远围绕三件事展开状态定义、转移方程、边界初始化。状态定义就是“dp[i] 表示什么”。这是整个DP最关键的一步状态定错了后面全错。转移方程描述的是状态之间的推导关系比如 dp[i] dp[i-1] dp[i-2] 这类。边界条件则是地基没有初始值后面的高楼根本没法盖。我在带新人时常说一句话先别急着写代码拿出纸笔把这行字写下来——“dp[i] 的含义是……转移关系是……初始条件是……”。只要你把这三行写清楚代码基本就是照着它们翻译。1.3 动态规划 VS 贪心别再把它们混为一谈很多人分不清DP和贪心尤其是遇到“跳跃游戏II”这种可以用贪心解的题时经常被搞晕。两者的核心差异在是否“回看历史”和“尝试所有可能”。贪心算法每一步只选择当前看起来最优的方案不做全局枚举所以它快但它要求每一步的局部最优能凑成全局最优。动态规划则不然它会枚举所有可能的状态转移路径相当于把每种情况都试一遍然后取最优。换句话说贪心是在一条路径上走到底DP是在一张状态网络上做全量搜索并取优。判断用哪个的原则很简单你能证明每一步的局部最优必然导向全局最优就用贪心证明不了老老实实DP。实际刷题中很多“最优解”类型的题目其实有贪心方案但DP是更通用的保底方案就算效率差一点至少能先解出来。2. 第一式到第三式最基础的三板斧降龙十八掌的前三掌是基本功动态规划也一样。一维线性DP、二维网格DP、背包问题这三类覆盖了绝大多数DP面试题的基础。把它们吃透了后面的区间DP、树形DP才有话可说。2.1 第一式一维线性DP——几乎所有DP入门的第一道坎一维线性DP是动态规划里形态最简单的一类状态只用一个维度表示转移也只依赖前一个或前几个状态。典型题目就是爬楼梯和打家劫舍。以爬楼梯为例题目是每次可以爬1级或2级台阶问爬到第n级有多少种不同的方法。定义 dp[i] 表示爬到第 i 级台阶的方案数因为最后一步要么从第 i-1 级跨1步上来要么从第 i-2 级跨2步上来所以状态转移方程就是def climbStairs(n: int) - int: if n 2: return n dp [0] * (n 1) dp[1] 1 dp[2] 2 for i in range(3, n 1): dp[i] dp[i - 1] dp[i - 2] return dp[n]这里的边界条件是 dp[1] 1、dp[2] 2。为什么这么定因为到第1级只有1种走法到第2级有2种11 或 2这是可以枚举出来的基础值也是递推的起点。我建议新手在学这类题时动手画一张“状态依赖图”把 dp[i]、dp[i-1]、dp[i-2] 画成三个圆圈用箭头表示依赖关系。你很快会发现这就是一张有向无环图而动态规划本质上是在这个DAG上做拓扑序递推。这个视角一旦建立后面很多复杂DP你都会觉得“不过如此”。2.2 第二式二维网格DP——从直线走到平面当问题变成矩阵、棋盘或两条路径的决策时一维状态就装不下了这时候需要二维DP。最常见的经典题是最小路径和给定一个 m×n 的网格每个格子里有数字从左上角走到右下角每次只能向右或向下走求路径上数字总和的最小值。状态定义很自然dp[i][j] 表示从左上角走到位置 (i, j) 的最小路径和。因为每次只能从左边或上边过来所以转移方程就是def minPathSum(grid): m, n len(grid), len(grid[0]) dp [[0] * n for _ in range(m)] dp[0][0] grid[0][0] # 初始化第一行只能从左边走过来 for j in range(1, n): dp[0][j] dp[0][j - 1] grid[0][j] # 初始化第一列只能从上边走下来 for i in range(1, m): dp[i][0] dp[i - 1][0] grid[i][0] # 正常递推 for i in range(1, m): for j in range(1, n): dp[i][j] min(dp[i - 1][j], dp[i][j - 1]) grid[i][j] return dp[m - 1][n - 1]写这类二维DP时有三个容易翻车的细节。第一是初始化顺序必须先处理第一行和第一列否则 dp[i][j] 的递推会引用到未定义的格子。第二是数组越界for 循环的起点必须从1开始把边界情况单独拎出来。第三是空间优化如果原题允许可以把二维dp压成一维只保留上一行的值这样空间复杂度从 O(mn) 降到 O(n)。压缩时注意从后往前更新避免覆盖还没用到的旧值。二维DP还经常以“不同路径”“最大正方形”“编辑距离”等形式出现。万变不离其宗只要你能把“位置”当作状态维度把“怎么走到这个位置”写成转移方程这类题就稳了。2.3 第三式背包问题——动态规划最硬的骨架背包问题是DP里最庞大的家族也是面试和竞赛中出现频率最高的题型。热词里的“01背包问题动态规划”“动态规划 资源分配”都跑不出这个框架。背包问题的本质是给你一堆物品每个物品有价值、有重量或体积背包有容量上限问能装下的最大价值。01背包是最基础的每个物品只能选一次。它的一维写法几乎是所有背包题的标准模板def zeroOneBag(weights, values, capacity): n len(weights) dp [0] * (capacity 1) for i in range(n): # 注意倒序遍历保证每个物品只选一次 for c in range(capacity, weights[i] - 1, -1): dp[c] max(dp[c], dp[c - weights[i]] values[i]) return dp[capacity]为什么内层循环要倒序这是01背包最重要的细节。因为 dp[c - weights[i]] 在正序遍历时可能已经被当前物品 i 更新过了如果用更新过的值再去更新 dp[c]就相当于同一个物品被拿了多次变成了完全背包。倒序可以保证 dp[c - weights[i]] 依然是上一轮没选当前物品的状态从而保证“每个物品只选一次”的语义。如果把内层循环改成正序就自动变成完全背包每个物品可以选无限次。这个对比特别重要我在面试中经常用一个问题考别人“01背包和完全背包代码里有什么区别”答案就是差一个遍历方向。还有个变体叫多重背包每个物品有数量限制。它可以通过二进制拆分转成若干个01背包物品来做思路是把一种物品按 1、2、4、8…… 拆成若干份然后当01背包处理。这个方法能显著减少物品数量是竞赛中的常见优化。“资源分配问题”其实也能用背包思路解。比如要把一定数量的资源分配给多个项目每个项目分配不同资源量会产生不同收益求总收益最大。这种题本质上就是一个完全背包的变体容量是总资源项目是“物品组”每个项目内的分配方案相当于互斥的“组内选项”所以要用分组背包的做法每组内只能选一种分配方案。3. 第四式到第六式中阶进阶三板斧基础三板斧能解决面试中相当一部分DP题但如果想打算法竞赛或者面对更复杂的面试题区间DP、记忆化搜索、状态压缩DP这三式就必须掌握。它们代表的思维模式跟前三类差别挺大值得单独拎出来讲。3.1 第四式区间DP——合并类问题的标准套路区间DP处理的场景通常是“在数组或字符串的某个区间内做操作求最优值”经典题是石子合并、戳气球、矩阵链乘。这类题的特点是一个区间的问题可以拆成两个子区间来解决最后合并两个子区间的结果。以石子合并为例有 N 堆石子排成一排每次只能合并相邻两堆合并的代价是两堆石子重量之和问把所有石子合并成一堆的最小总代价。状态定义是 dp[i][j] 表示合并第 i 堆到第 j 堆的最小代价。转移思路是枚举一个分割点 k把区间 [i, j] 分成 [i, k] 和 [k1, j]分别合并后再把这两堆合并def mergeStones(stones): n len(stones) prefix [0] * (n 1) for i in range(1, n 1): prefix[i] prefix[i - 1] stones[i - 1] dp [[0] * n for _ in range(n)] # 枚举区间长度从短到长 for length in range(2, n 1): for i in range(n - length 1): j i length - 1 dp[i][j] float(inf) for k in range(i, j): dp[i][j] min( dp[i][j], dp[i][k] dp[k 1][j] prefix[j 1] - prefix[i] ) return dp[0][n - 1] if n 0 else 0区间DP有一个很容易踩的坑循环顺序。必须先枚举区间长度 length再枚举左端点 i而不是先枚举 i 再枚举 j。原因很简单dp[i][j] 依赖的是更短区间的结果只有保证所有长度小于当前 length 的区间都已经算完了递推才是可靠的。另外石子合并有两个版本直线型和环形。环形只需把数组复制一份变成 2n 的长度最后在 n 个长度为 n 的区间里取最小值即可。这是区间DP里最常见的变体套路遇到环形问题先别慌拆环成链是最通用的解法。3.2 第五式记忆化搜索——从暴力递归到DP的天然桥梁很多人在学DP时最大的障碍是“怎么从问题直接写出状态转移方程”。我给出的建议是如果直接写递推有困难先写暴力递归再用记忆化加缓存。这就是记忆化搜索的思路也是自顶向下的DP。拿爬楼梯来举例最暴力的写法是递归def climbStairs(n: int) - int: if n 2: return n return climbStairs(n - 1) climbStairs(n - 2)这个写法正确但慢因为存在大量重复计算。记忆化的改造很简单用一个字典记录已经算过的结果def climbStairsWithMemo(n: int) - int: memo {} def dfs(x: int) - int: if x in memo: return memo[x] if x 2: return x memo[x] dfs(x - 1) dfs(x - 2) return memo[x] return dfs(n)对比一下就能发现记忆化搜索和自底向上的递推DP本质上是在算同一张表只是遍历顺序相反。前者从目标问题递归往下拆后者从边界条件迭代往上推。实际做题时记忆化搜索有一个巨大优势它天然贴合暴力递归的思考方式你不必一开始就设计出完整的DP循环结构只需要先把递归写对再加缓存就行。在复杂问题上比如树形DP、区间DP记忆化搜索甚至比递推更直观。我个人建议新手不要抗拒递归这恰恰是打通DP思维的最快路径。等你熟练之后再尝试把记忆化搜索改写成递推进一步提升效率和逼格。3.3 第六式状态压缩DP——当状态是一个集合有些DP题的状态不是单个数字而是一个“集合”。典型场景是旅行商问题TSP有 n 座城市从某城市出发每个城市恰好访问一次最后回到起点求最短路径。如果城市数 n 很小比如 n ≤ 20我们没办法用 dp[i] 表示“走完前i个城市的最短距离”因为“前i个城市”无法准确描述当前走到了哪个城市以及访问了哪些城市。这时候需要把“已经访问过的城市集合”压缩成一个整数用整数的二进制位表示集合中哪些元素被选中——这就是状态压缩DP。状态定义是 dp[mask][i]表示已经访问的城市集合是 mask当前所在城市是 i 时的最短路径长度。mask 是一个 n 位的二进制数第 k 位为1表示第 k 个城市已经被访问过。转移时枚举下一个未访问的城市 j更新 dp[mask | (1 j)][j]。import math def tsp(dist): n len(dist) dp [[math.inf] * n for _ in range(1 n)] dp[1][0] 0 # 从城市0出发只访问了城市0 for mask in range(1 n): for i in range(n): if not (mask (1 i)): continue for j in range(n): if mask (1 j): continue new_mask mask | (1 j) dp[new_mask][j] min(dp[new_mask][j], dp[mask][i] dist[i][j]) full_mask (1 n) - 1 ans min(dp[full_mask][i] dist[i][0] for i in range(1, n)) return ans状态压缩DP的常见陷阱是mask 的位数太多导致dp数组爆炸。所以它只适用于 n ≤ 20 左右的情况。一个重要的优化是可以先枚举 mask再枚举 i 和 j如果某些城市未访问就跳过能把无效状态剪掉不少。这类题目的代码模板高度统一多写几次自然就熟了。4. 第七式到第十式高阶套路与优化心法如果把前面六式当成“招式”那这四式更像“心法”和“变招”。树形DP、数位DP应用面相对窄但遇到就必须会贪心与DP的分辨是考场上决定你能不能少走弯路的关键至于优化技巧它能把一道题目从“能过样例”变成“真的能满分过题”。4.1 第七式树形DP——在树上做决策关键在DFS树形DP就是状态定义在一棵树的节点上利用DFS自底向上或自顶向下递推。典型题目是打家劫舍III二叉树结构的房子相邻节点不能同时偷问最多能偷多少金额。这种题的转移不是简单的 i - i1而是父节点和子节点之间的依赖。每个节点有两个状态偷或不偷。如果父节点不偷两个子节点都可以随意选择如果父节点偷子节点都不偷。代码如下def rob(root): def dfs(node): if not node: return (0, 0) left dfs(node.left) right dfs(node.right) # 不偷当前节点子节点可偷可不偷取较大 not_rob max(left) max(right) # 偷当前节点子节点不能偷 rob_cur node.val left[0] right[0] return (not_rob, rob_cur) return max(dfs(root))树形DP最核心的两点一是确定递归边界空节点返回 (0, 0)二是明确每个节点的返回值我这里返回的是一个二元组分别表示不偷和偷时该子树能获得的最大金额。这种“每个节点返回一组状态值由父节点合并”的模式是树形DP的通用骨架。树形DP也经常和“树上背包”结合典型场景是树上的资源分配问题。比如每门课程有前置课程学完能得到一定学分问你最多能选几门课。这种题可以先用DFS把树构建出来然后对每个节点做一次01背包状态 dp[u][j] 表示在节点 u 的子树上选了 j 门课的最大收获。理解它的关键在于树形结构天然适合做分组背包因为每个子节点是一组你只能从一组里选有限个。4.2 第八式数位DP——按位处理的高频面试题数位DP专门用来解决“某个区间内满足某种性质的数字有多少个”这类问题比如“1 到 n 中不含数字4的数有多少个”。热词里的“算法是什么意思”也许有人会问其实这类题就是典型的数位计数问题。数位DP的核心思想是把数字一位一位地拆开利用状态 dp[pos][state] 表示“当前处理到第 pos 位前面位的状态是 state 时符合条件的数字个数”。除此之外还有一个关键概念叫limit表示当前位的取值是否受到 n 的约束。如果前一位已经比 n 的前缀小了当前位就可以在 0~9 之间自由选择否则当前位的上限是 n 的这一位。def countNumbers(n: int) - int: digits list(map(int, str(n))) from functools import lru_cache lru_cache(None) def dfs(pos, state, limit): if pos len(digits): return 1 # 合法数字返回1 res 0 up digits[pos] if limit else 9 for d in range(up 1): if d 4: continue # 跳过包含数字4的情况 res dfs(pos 1, state, limit and d up) return res return dfs(0, 0, True)数位DP有一个高频坑前导零。如果题目说“1到n之间”数字0通常不算但前导零在逐位DP里可能会被错误计入。解决办法是增加一个状态位专门记录“前面是否全是0”或者直接见题拆题根据题目要求调整初始化。这类题在面试中很适合考察候选人的“分情况讨论”能力所以大厂笔试很喜欢出。如果你想把数位DP练熟推荐重点做“不含某个数字的个数”“数字之和能被某个数整除的个数”“回文数字计数”这几类。4.3 第九式贪心与DP的分辨——很多题其实不用DP接着开头的话题再深入说一句。我在刷题时发现很多号称是DP的题实际用贪心会更简单。最典型的就是跳跃游戏II题目是给你一个数组每个元素表示从当前位置最多能跳多远问最少跳几次能到达最后一个位置。这题如果硬用DP做状态 dp[i] 表示跳到位置 i 的最少步数转移需要遍历所有能跳到 i 的位置复杂度是 O(n^2)在数组长度超过10万的时候会超时。但用贪心做只需要维护当前能到达的最远边界和步数一次遍历就能解决def jump(nums: List[int]) - int: n len(nums) jumps 0 cur_end 0 farthest 0 for i in range(n - 1): farthest max(farthest, i nums[i]) if i cur_end: jumps 1 cur_end farthest return jumps这个贪心能成立的根本原因是对于跳跃问题你在某一跳能覆盖的所有位置里选“能跳得更远”的那个位置是安全的因为更远的覆盖范围不会丢掉任何未来可达的位置局部最优一定导向全局最优。我分享一个经验法则看到“最少步数”“最小代价”先别急着上DP先想想是否存在单调性。如果题目具有“覆盖范围越远越好”这种单调性贪心几乎总是更优解。只有在无法证明贪心正确、或者题目明显是要你枚举所有组合时才回到DP保底。4.4 第十式空间与时间优化——让DP从能跑变成跑得快DP写对了是一回事能不能在限定时间内跑完是另一回事。我把最常用的几个优化手法列在一起它们在各种热词里的算法题中频繁出现。空间优化滚动数组如果在转移方程中dp[i] 只依赖 dp[i-1] 或 dp[i-2] 这类固定前驱状态就可以用变量滚动更新把空间复杂度从 O(n) 降到 O(1)。爬楼梯那题完全可以改写def climbStairsOptimized(n: int) - int: if n 2: return n prev2, prev1 1, 2 for _ in range(3, n 1): prev2, prev1 prev1, prev1 prev2 return prev1类似地二维网格DP可以压缩到一行背包问题的一维数组本身就是从二维滚动过来的。这个优化写起来不难关键是要在写代码前就想清楚当前状态到底依赖哪些历史状态。时间优化把 O(n^2) 压到 O(n log n) 最常见的手段是单调队列优化和斜率优化。前者适用于转移方程中有一个窗口范围限制的情况典型题是“滑动窗口内的最大值”和部分区间DP变体后者适用于转移方程形如 dp[i] min(dp[j] cost) 常量且 cost 中包含与 i、j 相关的乘积项的情况。这两类优化属于竞赛进阶内容面试通常不常见但如果你想冲刺ACM或者顶级笔试绕不开。另外一个很通用的优化技巧是状态剪枝在枚举转移时跳过明显不可能到达或不可能更优的状态。比如背包问题里如果总重量已经超过容量这个分支直接剪掉能省不少无谓运算。5. 实战复盘最少硬币问题的完整解题链路理论讲得再多不如完整走一遍题目。这一节我用热词里出现频率很高的“动态规划最少硬币 python”来做一个完整的实战复盘。题目是给定不同面额的硬币 coins 和一个总金额 amount求凑出该金额所需的最少硬币个数如果无法凑出则返回 -1。5.1 第一步从暴力递归到记忆化先跑通再谈优化很多人一上来就想写DP数组其实最短路径是先从暴力递归开始。定义 dfs(amount) 表示凑出 amount 需要的最少硬币个数。在递归函数里枚举每一种硬币如果 amount coin就尝试用这枚硬币然后递归求 dfs(amount - coin)最后取所有尝试里的最小值加1def coinChangeBruteForce(coins, amount): if amount 0: return 0 ans float(inf) for coin in coins: if amount coin: ans min(ans, 1 coinChangeBruteForce(coins, amount - coin)) return ans if ans ! float(inf) else -1这个版本能跑通小数据但效率极低。原因很简单amount100 时递归里会出现巨量的重复子问题。加上记忆化def coinChangeMemo(coins, amount): memo {} def dfs(n): if n in memo: return memo[n] if n 0: return 0 ans float(inf) for coin in coins: if n coin: ans min(ans, 1 dfs(n - coin)) memo[n] ans return ans res dfs(amount) return res if res ! float(inf) else -1把 memo 字典想象成一张“顺手记下来的小抄”每个金额对应的最少硬币数只算一次。这个版本的复杂度大约是 O(amount * len(coins))已经能通过大多数中等难度的OJ数据了。5.2 第二步从记忆化到自底向上的标准动态规划记忆化搜索是自顶向下而标准的DP写法是自底向上。两者的转移方程其实一样关键在于dp数组的定义dp[i] 表示凑出金额 i 所需的最少硬币个数。初始化 dp[0] 0其余 dp[i] 初始化为一个很大的数比如 float(inf)表示“还没凑出来”。然后从 1 到 amount 遍历每个金额对每个金额尝试所有硬币面额def coinChange(coins, amount): dp [float(inf)] * (amount 1) dp[0] 0 for i in range(1, amount 1): for coin in coins: if i coin: dp[i] min(dp[i], dp[i - coin] 1) return dp[amount] if dp[amount] ! float(inf) else -1这段代码简洁、直观、不容易出错。很多资料把这个题归类为完全背包问题硬币数量无限总“容量”是 amount每个硬币的“价值”是1目标是总个数最少。和01背包的区别在于这里不需要倒序遍历 dp 数组因为硬币可以重复使用。一个小细节值得提醒dp 数组初始化的“无穷大”到底用多少我建议用 float(inf) 或者一个大于金额的数比如 amount 1。因为任何可行解最多用 amount 个1元硬币假设有1元面额所以 amount 1 在数值上足够大且不会溢出后续做 min 比较时不会干扰正常结果。5.3 第三步扩展与变体——资源分配也能套同样思路最少硬币还有一个经典变体求方案数。题目改成“凑出 amount 有多少种组合方式”时DP方程就变成 dp[i] dp[i - coin]这对应完全背包的计数版本。我在做一次性资源分配问题时也常用这个模板比如给几个项目分配资金问刚好用完预算的方案数套的也是这同一个套路。另一个变体是每种硬币有数量限制这就是多重背包的计数问题需要把硬币按数量拆成几组或者用单调队列优化。我在面试中见过不少候选人能写出基础版本但一旦遇到“恰好用完”“求最小/最大”“计数”等变体就卡壳。其实这些变体就是在基础状态定义上做微调核心还是状态、转移、初始化这三件套。6. 常见问题与排查技巧这些坑我替你踩过了动态规划的细节非常多尤其是新手。我把自己刷题和带人过程中反复出现的坑整理成一份“避坑指南”每一类都附上排查思路能帮你省下大量调试时间。6.1 初始化错误漏了边界全盘皆输最常见的问题是边界初始化不当。比如爬楼梯忘记初始化 dp[1] 和 dp[2]或者二维网格DP忘记单独处理第一行和第一列结果一跑就数组越界或者返回奇怪的结果。我的排查办法是写完代码后手动模拟小规模数据。拿 n3 或 2×3 的网格把dp数组从头到尾手算一遍对比代码算出来的结果。如果对不上几乎可以肯定是边界条件写错。这个方法虽然原始但比看代码眼瞪眼高效得多。6.2 遍历顺序错误01背包和完全背包差一个方向这是背包问题里最经典的坑。01背包必须倒序遍历容量保证每个物品只能取一次完全背包必须正序遍历保证可以重复取。写错方向后程序通常不报错只会返回错误答案所以特别隐蔽。我的建议是把“为什么倒序”这个原理刻在脑子里。倒序时当前物品更新过的状态不会被更后面的容量用到正序时当前物品会被反复使用。任何背包题的代码写完先检查这个方向再检查容量循环的下界有没有写对。6.3 大数溢出与边界索引silent bug 的重灾区在C或Java里dp数组如果用 int 存遇到路径计数这种题型结果很容易爆掉。就算在Python里如果没养成取模习惯也可能会输出一个超长的整数导致格式错误。另外数组下标的边界问题也很常见比如区间DP里枚举 k 从 i 到 j-1多写一个等号就可能越界。针对这一问题我在代码评审时有个习惯所有DP相关的循环边界都单独写注释标明取值范围。比如 “# 区间长度 length 从 2 到 n”这样一眼就能发现多算了一位、少算了一位的问题。6.4 状态定义模糊一开始就想不清后面全白写比起前面那些技术性错误状态定义不清才是最难排查的问题。我见过很多人写DP写到一半卡住代码里临时拼凑逻辑最终跑出来一个错误结果。这种情况往往不是因为代码语法有问题而是状态本身就没定义清楚。如果你发现自己写不下去了停下代码回去把三件事重新写一遍dp[i]或dp[i][j]的含义是什么它从哪些子状态转移而来边界值是什么我遇到过很多次答案在我重新梳理状态定义时自己浮出水面。这个方法听起来朴素但真的是最管用的调试方式。6.5 学习路径建议从套路到变式再到脱离模板最后分享一下我一直向身边人推荐的DP学习路径。第一阶段把线性DP、网格DP、背包问题吃透做到看到类似题能秒看出类型第二阶段集中练习区间DP、树形DP、数位DP和状态压缩DP重点体会“状态维度的选择”这件事第三阶段大量刷真题把每道题归入自己的“招式库”同时做空间和时间优化训练。我在实战中越来越体会到学习算法不能只看题解要亲手把每类DP的模板题写三遍以上直到合上代码也能默写出来。遇到不会的题时先对照“十式”看它属于哪一类然后套对应的状态定义框架。这套方法我已经推荐给很多朋友反馈普遍是“DP好像也没那么吓人了”。动态规划这条路入门靠套路精进靠积累。希望这“十式”能帮你把分散的知识点串成一条线以后再遇到DP题脑海里能第一时间浮现该用哪一掌。 
长河君 · 2026/9/14 10:44:32 · 阅读 1.2k 动态规划十式：从基础到进阶的完整解题框架
标题“动态规划十式”这个说法我觉得挺贴切尤其是拿降龙十八掌来类比。动态规划在算法领域的地位说一句“武林绝学”真不夸张——大厂笔试爱考算法竞赛必考就连日常写业务代码偶尔也会蹦出个优化需求逼着你用上它。但很多人一开始看到“状态转移方程”这几个字就懵了觉得这东西太抽象、太难上手。其实动态规划不是靠天赋而是靠套路。我在刷题和带新人的过程中慢慢发现看起来五花八门的DP题翻来覆去就那么十几类板子。你只要把每类的题目特征、状态定义方式、转移方程的写法记清楚再配合足够的训练量考场上遇到DP题基本能稳定拿分。所以这篇文章我想把这几年积累的DP套路整理成“十式”从最简单的线性DP一直讲到状态压缩、树形DP和各类优化技巧每式配一个经典例题再额外补一个完整的最少硬币问题实战流程帮你在脑内建立一套可以反复调用的解题框架。1. 动态规划到底是什么先破解三个底层概念想学招式先得明白内功心法。很多人学DP失败是因为连最基础的概念都模模糊糊直接从题目开始结果越学越乱。所以这一节我先把动态规划的底层逻辑撕开讲清楚。1.1 动态规划解决的问题重叠子问题和最优子结构动态规划最擅长解决的是“最优化问题”和“计数问题”——比如最大收益、最少次数、方案总数。这类问题有一个共同特征大问题的解可以由小问题的解推导出来而且这些小问题会被反复计算。这背后涉及两个关键性质。第一个叫最优子结构意思是原问题的最优解包含了子问题的最优解我一般跟别人解释就是“你每一步都选当前阶段的最优最后拼起来就是全局最优”。第二个叫重叠子问题指的是不同的决策路径会碰到同一个子问题。举个例子你在爬一节一节楼梯时不管之前是走1步还是2步上来的到达第5层之后再往上走的方案数都一样。这个“第5层以后的方案”就被反复用到了。如果一个问题同时具备这两个性质那它大概率可以用DP解决。如果只有最优子结构、没有重叠子问题那用贪心或者分治法更合适如果有重叠子问题但不要求最优那可能是纯计数问题DP依然是好选择。1.2 状态、转移方程、边界条件三件套缺一不可动态规划的代码模板其实特别固定永远围绕三件事展开状态定义、转移方程、边界初始化。状态定义就是“dp[i] 表示什么”。这是整个DP最关键的一步状态定错了后面全错。转移方程描述的是状态之间的推导关系比如 dp[i] dp[i-1] dp[i-2] 这类。边界条件则是地基没有初始值后面的高楼根本没法盖。我在带新人时常说一句话先别急着写代码拿出纸笔把这行字写下来——“dp[i] 的含义是……转移关系是……初始条件是……”。只要你把这三行写清楚代码基本就是照着它们翻译。1.3 动态规划 VS 贪心别再把它们混为一谈很多人分不清DP和贪心尤其是遇到“跳跃游戏II”这种可以用贪心解的题时经常被搞晕。两者的核心差异在是否“回看历史”和“尝试所有可能”。贪心算法每一步只选择当前看起来最优的方案不做全局枚举所以它快但它要求每一步的局部最优能凑成全局最优。动态规划则不然它会枚举所有可能的状态转移路径相当于把每种情况都试一遍然后取最优。换句话说贪心是在一条路径上走到底DP是在一张状态网络上做全量搜索并取优。判断用哪个的原则很简单你能证明每一步的局部最优必然导向全局最优就用贪心证明不了老老实实DP。实际刷题中很多“最优解”类型的题目其实有贪心方案但DP是更通用的保底方案就算效率差一点至少能先解出来。2. 第一式到第三式最基础的三板斧降龙十八掌的前三掌是基本功动态规划也一样。一维线性DP、二维网格DP、背包问题这三类覆盖了绝大多数DP面试题的基础。把它们吃透了后面的区间DP、树形DP才有话可说。2.1 第一式一维线性DP——几乎所有DP入门的第一道坎一维线性DP是动态规划里形态最简单的一类状态只用一个维度表示转移也只依赖前一个或前几个状态。典型题目就是爬楼梯和打家劫舍。以爬楼梯为例题目是每次可以爬1级或2级台阶问爬到第n级有多少种不同的方法。定义 dp[i] 表示爬到第 i 级台阶的方案数因为最后一步要么从第 i-1 级跨1步上来要么从第 i-2 级跨2步上来所以状态转移方程就是def climbStairs(n: int) - int: if n 2: return n dp [0] * (n 1) dp[1] 1 dp[2] 2 for i in range(3, n 1): dp[i] dp[i - 1] dp[i - 2] return dp[n]这里的边界条件是 dp[1] 1、dp[2] 2。为什么这么定因为到第1级只有1种走法到第2级有2种11 或 2这是可以枚举出来的基础值也是递推的起点。我建议新手在学这类题时动手画一张“状态依赖图”把 dp[i]、dp[i-1]、dp[i-2] 画成三个圆圈用箭头表示依赖关系。你很快会发现这就是一张有向无环图而动态规划本质上是在这个DAG上做拓扑序递推。这个视角一旦建立后面很多复杂DP你都会觉得“不过如此”。2.2 第二式二维网格DP——从直线走到平面当问题变成矩阵、棋盘或两条路径的决策时一维状态就装不下了这时候需要二维DP。最常见的经典题是最小路径和给定一个 m×n 的网格每个格子里有数字从左上角走到右下角每次只能向右或向下走求路径上数字总和的最小值。状态定义很自然dp[i][j] 表示从左上角走到位置 (i, j) 的最小路径和。因为每次只能从左边或上边过来所以转移方程就是def minPathSum(grid): m, n len(grid), len(grid[0]) dp [[0] * n for _ in range(m)] dp[0][0] grid[0][0] # 初始化第一行只能从左边走过来 for j in range(1, n): dp[0][j] dp[0][j - 1] grid[0][j] # 初始化第一列只能从上边走下来 for i in range(1, m): dp[i][0] dp[i - 1][0] grid[i][0] # 正常递推 for i in range(1, m): for j in range(1, n): dp[i][j] min(dp[i - 1][j], dp[i][j - 1]) grid[i][j] return dp[m - 1][n - 1]写这类二维DP时有三个容易翻车的细节。第一是初始化顺序必须先处理第一行和第一列否则 dp[i][j] 的递推会引用到未定义的格子。第二是数组越界for 循环的起点必须从1开始把边界情况单独拎出来。第三是空间优化如果原题允许可以把二维dp压成一维只保留上一行的值这样空间复杂度从 O(mn) 降到 O(n)。压缩时注意从后往前更新避免覆盖还没用到的旧值。二维DP还经常以“不同路径”“最大正方形”“编辑距离”等形式出现。万变不离其宗只要你能把“位置”当作状态维度把“怎么走到这个位置”写成转移方程这类题就稳了。2.3 第三式背包问题——动态规划最硬的骨架背包问题是DP里最庞大的家族也是面试和竞赛中出现频率最高的题型。热词里的“01背包问题动态规划”“动态规划 资源分配”都跑不出这个框架。背包问题的本质是给你一堆物品每个物品有价值、有重量或体积背包有容量上限问能装下的最大价值。01背包是最基础的每个物品只能选一次。它的一维写法几乎是所有背包题的标准模板def zeroOneBag(weights, values, capacity): n len(weights) dp [0] * (capacity 1) for i in range(n): # 注意倒序遍历保证每个物品只选一次 for c in range(capacity, weights[i] - 1, -1): dp[c] max(dp[c], dp[c - weights[i]] values[i]) return dp[capacity]为什么内层循环要倒序这是01背包最重要的细节。因为 dp[c - weights[i]] 在正序遍历时可能已经被当前物品 i 更新过了如果用更新过的值再去更新 dp[c]就相当于同一个物品被拿了多次变成了完全背包。倒序可以保证 dp[c - weights[i]] 依然是上一轮没选当前物品的状态从而保证“每个物品只选一次”的语义。如果把内层循环改成正序就自动变成完全背包每个物品可以选无限次。这个对比特别重要我在面试中经常用一个问题考别人“01背包和完全背包代码里有什么区别”答案就是差一个遍历方向。还有个变体叫多重背包每个物品有数量限制。它可以通过二进制拆分转成若干个01背包物品来做思路是把一种物品按 1、2、4、8…… 拆成若干份然后当01背包处理。这个方法能显著减少物品数量是竞赛中的常见优化。“资源分配问题”其实也能用背包思路解。比如要把一定数量的资源分配给多个项目每个项目分配不同资源量会产生不同收益求总收益最大。这种题本质上就是一个完全背包的变体容量是总资源项目是“物品组”每个项目内的分配方案相当于互斥的“组内选项”所以要用分组背包的做法每组内只能选一种分配方案。3. 第四式到第六式中阶进阶三板斧基础三板斧能解决面试中相当一部分DP题但如果想打算法竞赛或者面对更复杂的面试题区间DP、记忆化搜索、状态压缩DP这三式就必须掌握。它们代表的思维模式跟前三类差别挺大值得单独拎出来讲。3.1 第四式区间DP——合并类问题的标准套路区间DP处理的场景通常是“在数组或字符串的某个区间内做操作求最优值”经典题是石子合并、戳气球、矩阵链乘。这类题的特点是一个区间的问题可以拆成两个子区间来解决最后合并两个子区间的结果。以石子合并为例有 N 堆石子排成一排每次只能合并相邻两堆合并的代价是两堆石子重量之和问把所有石子合并成一堆的最小总代价。状态定义是 dp[i][j] 表示合并第 i 堆到第 j 堆的最小代价。转移思路是枚举一个分割点 k把区间 [i, j] 分成 [i, k] 和 [k1, j]分别合并后再把这两堆合并def mergeStones(stones): n len(stones) prefix [0] * (n 1) for i in range(1, n 1): prefix[i] prefix[i - 1] stones[i - 1] dp [[0] * n for _ in range(n)] # 枚举区间长度从短到长 for length in range(2, n 1): for i in range(n - length 1): j i length - 1 dp[i][j] float(inf) for k in range(i, j): dp[i][j] min( dp[i][j], dp[i][k] dp[k 1][j] prefix[j 1] - prefix[i] ) return dp[0][n - 1] if n 0 else 0区间DP有一个很容易踩的坑循环顺序。必须先枚举区间长度 length再枚举左端点 i而不是先枚举 i 再枚举 j。原因很简单dp[i][j] 依赖的是更短区间的结果只有保证所有长度小于当前 length 的区间都已经算完了递推才是可靠的。另外石子合并有两个版本直线型和环形。环形只需把数组复制一份变成 2n 的长度最后在 n 个长度为 n 的区间里取最小值即可。这是区间DP里最常见的变体套路遇到环形问题先别慌拆环成链是最通用的解法。3.2 第五式记忆化搜索——从暴力递归到DP的天然桥梁很多人在学DP时最大的障碍是“怎么从问题直接写出状态转移方程”。我给出的建议是如果直接写递推有困难先写暴力递归再用记忆化加缓存。这就是记忆化搜索的思路也是自顶向下的DP。拿爬楼梯来举例最暴力的写法是递归def climbStairs(n: int) - int: if n 2: return n return climbStairs(n - 1) climbStairs(n - 2)这个写法正确但慢因为存在大量重复计算。记忆化的改造很简单用一个字典记录已经算过的结果def climbStairsWithMemo(n: int) - int: memo {} def dfs(x: int) - int: if x in memo: return memo[x] if x 2: return x memo[x] dfs(x - 1) dfs(x - 2) return memo[x] return dfs(n)对比一下就能发现记忆化搜索和自底向上的递推DP本质上是在算同一张表只是遍历顺序相反。前者从目标问题递归往下拆后者从边界条件迭代往上推。实际做题时记忆化搜索有一个巨大优势它天然贴合暴力递归的思考方式你不必一开始就设计出完整的DP循环结构只需要先把递归写对再加缓存就行。在复杂问题上比如树形DP、区间DP记忆化搜索甚至比递推更直观。我个人建议新手不要抗拒递归这恰恰是打通DP思维的最快路径。等你熟练之后再尝试把记忆化搜索改写成递推进一步提升效率和逼格。3.3 第六式状态压缩DP——当状态是一个集合有些DP题的状态不是单个数字而是一个“集合”。典型场景是旅行商问题TSP有 n 座城市从某城市出发每个城市恰好访问一次最后回到起点求最短路径。如果城市数 n 很小比如 n ≤ 20我们没办法用 dp[i] 表示“走完前i个城市的最短距离”因为“前i个城市”无法准确描述当前走到了哪个城市以及访问了哪些城市。这时候需要把“已经访问过的城市集合”压缩成一个整数用整数的二进制位表示集合中哪些元素被选中——这就是状态压缩DP。状态定义是 dp[mask][i]表示已经访问的城市集合是 mask当前所在城市是 i 时的最短路径长度。mask 是一个 n 位的二进制数第 k 位为1表示第 k 个城市已经被访问过。转移时枚举下一个未访问的城市 j更新 dp[mask | (1 j)][j]。import math def tsp(dist): n len(dist) dp [[math.inf] * n for _ in range(1 n)] dp[1][0] 0 # 从城市0出发只访问了城市0 for mask in range(1 n): for i in range(n): if not (mask (1 i)): continue for j in range(n): if mask (1 j): continue new_mask mask | (1 j) dp[new_mask][j] min(dp[new_mask][j], dp[mask][i] dist[i][j]) full_mask (1 n) - 1 ans min(dp[full_mask][i] dist[i][0] for i in range(1, n)) return ans状态压缩DP的常见陷阱是mask 的位数太多导致dp数组爆炸。所以它只适用于 n ≤ 20 左右的情况。一个重要的优化是可以先枚举 mask再枚举 i 和 j如果某些城市未访问就跳过能把无效状态剪掉不少。这类题目的代码模板高度统一多写几次自然就熟了。4. 第七式到第十式高阶套路与优化心法如果把前面六式当成“招式”那这四式更像“心法”和“变招”。树形DP、数位DP应用面相对窄但遇到就必须会贪心与DP的分辨是考场上决定你能不能少走弯路的关键至于优化技巧它能把一道题目从“能过样例”变成“真的能满分过题”。4.1 第七式树形DP——在树上做决策关键在DFS树形DP就是状态定义在一棵树的节点上利用DFS自底向上或自顶向下递推。典型题目是打家劫舍III二叉树结构的房子相邻节点不能同时偷问最多能偷多少金额。这种题的转移不是简单的 i - i1而是父节点和子节点之间的依赖。每个节点有两个状态偷或不偷。如果父节点不偷两个子节点都可以随意选择如果父节点偷子节点都不偷。代码如下def rob(root): def dfs(node): if not node: return (0, 0) left dfs(node.left) right dfs(node.right) # 不偷当前节点子节点可偷可不偷取较大 not_rob max(left) max(right) # 偷当前节点子节点不能偷 rob_cur node.val left[0] right[0] return (not_rob, rob_cur) return max(dfs(root))树形DP最核心的两点一是确定递归边界空节点返回 (0, 0)二是明确每个节点的返回值我这里返回的是一个二元组分别表示不偷和偷时该子树能获得的最大金额。这种“每个节点返回一组状态值由父节点合并”的模式是树形DP的通用骨架。树形DP也经常和“树上背包”结合典型场景是树上的资源分配问题。比如每门课程有前置课程学完能得到一定学分问你最多能选几门课。这种题可以先用DFS把树构建出来然后对每个节点做一次01背包状态 dp[u][j] 表示在节点 u 的子树上选了 j 门课的最大收获。理解它的关键在于树形结构天然适合做分组背包因为每个子节点是一组你只能从一组里选有限个。4.2 第八式数位DP——按位处理的高频面试题数位DP专门用来解决“某个区间内满足某种性质的数字有多少个”这类问题比如“1 到 n 中不含数字4的数有多少个”。热词里的“算法是什么意思”也许有人会问其实这类题就是典型的数位计数问题。数位DP的核心思想是把数字一位一位地拆开利用状态 dp[pos][state] 表示“当前处理到第 pos 位前面位的状态是 state 时符合条件的数字个数”。除此之外还有一个关键概念叫limit表示当前位的取值是否受到 n 的约束。如果前一位已经比 n 的前缀小了当前位就可以在 0~9 之间自由选择否则当前位的上限是 n 的这一位。def countNumbers(n: int) - int: digits list(map(int, str(n))) from functools import lru_cache lru_cache(None) def dfs(pos, state, limit): if pos len(digits): return 1 # 合法数字返回1 res 0 up digits[pos] if limit else 9 for d in range(up 1): if d 4: continue # 跳过包含数字4的情况 res dfs(pos 1, state, limit and d up) return res return dfs(0, 0, True)数位DP有一个高频坑前导零。如果题目说“1到n之间”数字0通常不算但前导零在逐位DP里可能会被错误计入。解决办法是增加一个状态位专门记录“前面是否全是0”或者直接见题拆题根据题目要求调整初始化。这类题在面试中很适合考察候选人的“分情况讨论”能力所以大厂笔试很喜欢出。如果你想把数位DP练熟推荐重点做“不含某个数字的个数”“数字之和能被某个数整除的个数”“回文数字计数”这几类。4.3 第九式贪心与DP的分辨——很多题其实不用DP接着开头的话题再深入说一句。我在刷题时发现很多号称是DP的题实际用贪心会更简单。最典型的就是跳跃游戏II题目是给你一个数组每个元素表示从当前位置最多能跳多远问最少跳几次能到达最后一个位置。这题如果硬用DP做状态 dp[i] 表示跳到位置 i 的最少步数转移需要遍历所有能跳到 i 的位置复杂度是 O(n^2)在数组长度超过10万的时候会超时。但用贪心做只需要维护当前能到达的最远边界和步数一次遍历就能解决def jump(nums: List[int]) - int: n len(nums) jumps 0 cur_end 0 farthest 0 for i in range(n - 1): farthest max(farthest, i nums[i]) if i cur_end: jumps 1 cur_end farthest return jumps这个贪心能成立的根本原因是对于跳跃问题你在某一跳能覆盖的所有位置里选“能跳得更远”的那个位置是安全的因为更远的覆盖范围不会丢掉任何未来可达的位置局部最优一定导向全局最优。我分享一个经验法则看到“最少步数”“最小代价”先别急着上DP先想想是否存在单调性。如果题目具有“覆盖范围越远越好”这种单调性贪心几乎总是更优解。只有在无法证明贪心正确、或者题目明显是要你枚举所有组合时才回到DP保底。4.4 第十式空间与时间优化——让DP从能跑变成跑得快DP写对了是一回事能不能在限定时间内跑完是另一回事。我把最常用的几个优化手法列在一起它们在各种热词里的算法题中频繁出现。空间优化滚动数组如果在转移方程中dp[i] 只依赖 dp[i-1] 或 dp[i-2] 这类固定前驱状态就可以用变量滚动更新把空间复杂度从 O(n) 降到 O(1)。爬楼梯那题完全可以改写def climbStairsOptimized(n: int) - int: if n 2: return n prev2, prev1 1, 2 for _ in range(3, n 1): prev2, prev1 prev1, prev1 prev2 return prev1类似地二维网格DP可以压缩到一行背包问题的一维数组本身就是从二维滚动过来的。这个优化写起来不难关键是要在写代码前就想清楚当前状态到底依赖哪些历史状态。时间优化把 O(n^2) 压到 O(n log n) 最常见的手段是单调队列优化和斜率优化。前者适用于转移方程中有一个窗口范围限制的情况典型题是“滑动窗口内的最大值”和部分区间DP变体后者适用于转移方程形如 dp[i] min(dp[j] cost) 常量且 cost 中包含与 i、j 相关的乘积项的情况。这两类优化属于竞赛进阶内容面试通常不常见但如果你想冲刺ACM或者顶级笔试绕不开。另外一个很通用的优化技巧是状态剪枝在枚举转移时跳过明显不可能到达或不可能更优的状态。比如背包问题里如果总重量已经超过容量这个分支直接剪掉能省不少无谓运算。5. 实战复盘最少硬币问题的完整解题链路理论讲得再多不如完整走一遍题目。这一节我用热词里出现频率很高的“动态规划最少硬币 python”来做一个完整的实战复盘。题目是给定不同面额的硬币 coins 和一个总金额 amount求凑出该金额所需的最少硬币个数如果无法凑出则返回 -1。5.1 第一步从暴力递归到记忆化先跑通再谈优化很多人一上来就想写DP数组其实最短路径是先从暴力递归开始。定义 dfs(amount) 表示凑出 amount 需要的最少硬币个数。在递归函数里枚举每一种硬币如果 amount coin就尝试用这枚硬币然后递归求 dfs(amount - coin)最后取所有尝试里的最小值加1def coinChangeBruteForce(coins, amount): if amount 0: return 0 ans float(inf) for coin in coins: if amount coin: ans min(ans, 1 coinChangeBruteForce(coins, amount - coin)) return ans if ans ! float(inf) else -1这个版本能跑通小数据但效率极低。原因很简单amount100 时递归里会出现巨量的重复子问题。加上记忆化def coinChangeMemo(coins, amount): memo {} def dfs(n): if n in memo: return memo[n] if n 0: return 0 ans float(inf) for coin in coins: if n coin: ans min(ans, 1 dfs(n - coin)) memo[n] ans return ans res dfs(amount) return res if res ! float(inf) else -1把 memo 字典想象成一张“顺手记下来的小抄”每个金额对应的最少硬币数只算一次。这个版本的复杂度大约是 O(amount * len(coins))已经能通过大多数中等难度的OJ数据了。5.2 第二步从记忆化到自底向上的标准动态规划记忆化搜索是自顶向下而标准的DP写法是自底向上。两者的转移方程其实一样关键在于dp数组的定义dp[i] 表示凑出金额 i 所需的最少硬币个数。初始化 dp[0] 0其余 dp[i] 初始化为一个很大的数比如 float(inf)表示“还没凑出来”。然后从 1 到 amount 遍历每个金额对每个金额尝试所有硬币面额def coinChange(coins, amount): dp [float(inf)] * (amount 1) dp[0] 0 for i in range(1, amount 1): for coin in coins: if i coin: dp[i] min(dp[i], dp[i - coin] 1) return dp[amount] if dp[amount] ! float(inf) else -1这段代码简洁、直观、不容易出错。很多资料把这个题归类为完全背包问题硬币数量无限总“容量”是 amount每个硬币的“价值”是1目标是总个数最少。和01背包的区别在于这里不需要倒序遍历 dp 数组因为硬币可以重复使用。一个小细节值得提醒dp 数组初始化的“无穷大”到底用多少我建议用 float(inf) 或者一个大于金额的数比如 amount 1。因为任何可行解最多用 amount 个1元硬币假设有1元面额所以 amount 1 在数值上足够大且不会溢出后续做 min 比较时不会干扰正常结果。5.3 第三步扩展与变体——资源分配也能套同样思路最少硬币还有一个经典变体求方案数。题目改成“凑出 amount 有多少种组合方式”时DP方程就变成 dp[i] dp[i - coin]这对应完全背包的计数版本。我在做一次性资源分配问题时也常用这个模板比如给几个项目分配资金问刚好用完预算的方案数套的也是这同一个套路。另一个变体是每种硬币有数量限制这就是多重背包的计数问题需要把硬币按数量拆成几组或者用单调队列优化。我在面试中见过不少候选人能写出基础版本但一旦遇到“恰好用完”“求最小/最大”“计数”等变体就卡壳。其实这些变体就是在基础状态定义上做微调核心还是状态、转移、初始化这三件套。6. 常见问题与排查技巧这些坑我替你踩过了动态规划的细节非常多尤其是新手。我把自己刷题和带人过程中反复出现的坑整理成一份“避坑指南”每一类都附上排查思路能帮你省下大量调试时间。6.1 初始化错误漏了边界全盘皆输最常见的问题是边界初始化不当。比如爬楼梯忘记初始化 dp[1] 和 dp[2]或者二维网格DP忘记单独处理第一行和第一列结果一跑就数组越界或者返回奇怪的结果。我的排查办法是写完代码后手动模拟小规模数据。拿 n3 或 2×3 的网格把dp数组从头到尾手算一遍对比代码算出来的结果。如果对不上几乎可以肯定是边界条件写错。这个方法虽然原始但比看代码眼瞪眼高效得多。6.2 遍历顺序错误01背包和完全背包差一个方向这是背包问题里最经典的坑。01背包必须倒序遍历容量保证每个物品只能取一次完全背包必须正序遍历保证可以重复取。写错方向后程序通常不报错只会返回错误答案所以特别隐蔽。我的建议是把“为什么倒序”这个原理刻在脑子里。倒序时当前物品更新过的状态不会被更后面的容量用到正序时当前物品会被反复使用。任何背包题的代码写完先检查这个方向再检查容量循环的下界有没有写对。6.3 大数溢出与边界索引silent bug 的重灾区在C或Java里dp数组如果用 int 存遇到路径计数这种题型结果很容易爆掉。就算在Python里如果没养成取模习惯也可能会输出一个超长的整数导致格式错误。另外数组下标的边界问题也很常见比如区间DP里枚举 k 从 i 到 j-1多写一个等号就可能越界。针对这一问题我在代码评审时有个习惯所有DP相关的循环边界都单独写注释标明取值范围。比如 “# 区间长度 length 从 2 到 n”这样一眼就能发现多算了一位、少算了一位的问题。6.4 状态定义模糊一开始就想不清后面全白写比起前面那些技术性错误状态定义不清才是最难排查的问题。我见过很多人写DP写到一半卡住代码里临时拼凑逻辑最终跑出来一个错误结果。这种情况往往不是因为代码语法有问题而是状态本身就没定义清楚。如果你发现自己写不下去了停下代码回去把三件事重新写一遍dp[i]或dp[i][j]的含义是什么它从哪些子状态转移而来边界值是什么我遇到过很多次答案在我重新梳理状态定义时自己浮出水面。这个方法听起来朴素但真的是最管用的调试方式。6.5 学习路径建议从套路到变式再到脱离模板最后分享一下我一直向身边人推荐的DP学习路径。第一阶段把线性DP、网格DP、背包问题吃透做到看到类似题能秒看出类型第二阶段集中练习区间DP、树形DP、数位DP和状态压缩DP重点体会“状态维度的选择”这件事第三阶段大量刷真题把每道题归入自己的“招式库”同时做空间和时间优化训练。我在实战中越来越体会到学习算法不能只看题解要亲手把每类DP的模板题写三遍以上直到合上代码也能默写出来。遇到不会的题时先对照“十式”看它属于哪一类然后套对应的状态定义框架。这套方法我已经推荐给很多朋友反馈普遍是“DP好像也没那么吓人了”。动态规划这条路入门靠套路精进靠积累。希望这“十式”能帮你把分散的知识点串成一条线以后再遇到DP题脑海里能第一时间浮现该用哪一掌。