1. 动态规划为什么是面试“钉子户”如果你刷过一阵子算法题会发现动态规划几乎出现在每一场像样的技术面试里。不管是校招还是社招面试官总喜欢拿一道DP题来试探候选人的思维深度——不是看你背了多少题而是看你能不能把一个大问题拆成小问题能不能从小问题的答案一步步推出大问题的答案。这个思维过程恰恰是日常工程里解决复杂问题最需要的能力。我面试别人时有个习惯先让候选人做一道中等难度的DP题。如果他能把状态定义讲清楚、把转移方程推导出来哪怕最后代码没写完我也会给不错的评价。因为DP题的核心不在于代码量而在于建模能力。反过来如果候选人上来就背着模板套题一旦题目变形就卡住那基本可以确定他的算法功底是浮的。这篇文章我打算系统梳理经典动态规划里最高频的几类题型包括它们的状态设计思路、转移方程推导过程、初始化细节、遍历顺序的讲究以及我在实际刷题和面试中踩过的坑。内容面向正准备面试的读者也适合学完基础DP但想加深理解的人。全篇围绕一个目标让你遇到一道新DP题时能有一套清晰可复用的思考路径而不是靠运气蒙。2. 先建立DP的正确认知状态、转移、初始化、遍历顺序2.1 DP的本质用子问题的答案组合出原问题的答案很多初学者一上来就背“最优子结构”“无后效性”这些术语背得滚瓜烂熟做题还是一脸懵。我更喜欢用一个生活化的类比来解释。假设你想知道从一楼爬到十楼一共有多少种走法每次可以走一级或两级台阶。这个问题如果你从十楼往下看会发现到达十楼的最后一步要么是从九楼跨一级上来要么是从八楼跨两级上来。那么到达十楼的总走法就等于到达九楼的走法加上到达八楼的走法。这就是最典型的DP思路——不直接去枚举所有路径而是先去解决更小的子问题然后用子问题的答案组合出大问题的答案。这个过程有两个关键点。第一子问题之间是重叠的同一个子问题会被反复用到所以需要把计算结果存下来避免重复计算。第二每个子问题只关心自己的答案不关心它是怎么得到的这就是“无后效性”的通俗解释——过去的具体路径不影响未来的决策。你在面试中讲DP题时如果能用这种直白的语言把本质讲清楚面试官通常会挺认可。因为这说明你不是在背题而是真的理解了DP之所以高效的原因——用空间换时间把指数级枚举降成多项式级计算。2.2 一个DP题的标准构成四个要素缺一不可我习惯把每一道DP题都拆成四个要素来审视状态定义dp数组的每个元素代表什么含义转移方程当前状态如何由之前的状态推导出来初始化边界状态是什么dp数组的起点值怎么设定遍历顺序按什么顺序填表才能保证推导某个状态时它依赖的状态已经算好了这四个要素里状态定义是灵魂也是最难的一步。同一个题目状态定义得好转移方程可能只写一行定义得不好可能要写好几行甚至根本推不出来。比如经典的LIS问题最长递增子序列有人定义dp[i]为“以第i个元素结尾的最长递增子序列长度”转移就非常自然遍历i之前的所有j如果nums[j] nums[i]就用dp[j] 1来更新dp[i]。这个定义把焦点放在“结尾元素”上就能自然地利用子问题的性质。而初始化则是很多人容易忽略的地方但它直接决定正确性。比如斐波那契数列的dp[0]和dp[1]如果没设置对后面全是错的。再比如背包问题里dp[0]表示容量为0时能装的最大价值这个边界必须为0否则后续推导就不成立。遍历顺序也很有讲究。二维DP里外层循环遍历物品还是遍历容量结果可能完全不同一维滚动数组里遍历容量必须倒序否则同一个物品会被重复使用——这是01背包问题里最容易出错的地方后面我会专门展开讲。2.3 DP和递归、贪心的分界线在哪里面试中经常被追问的一个问题是“这道题你为什么不递归做为什么不用贪心”你需要能清晰地划出分界线。递归和DP的关系其实很近递归是自顶向下DP是自底向上。递归写起来直观但如果没有记忆化复杂度是指数级的有了记忆化本质上就是DP的另一种写法。所以有些题目你用递归加缓存也能过但面试时我更推荐用迭代的DP写法因为它空间占用更容易控制也面试官也更容易看清你的思路。贪心和DP的区别更微妙。贪心每一步都做当前看起来最优的选择不考虑未来DP则考虑所有可能的选择并从中取最优。判断标准很简单如果局部最优能推出全局最优用贪心如果不行就用DP。比如找零钱问题如果硬币面额是1、5、11要找15元贪心会先拿11再拿4个1得到5枚硬币但最优解是3枚5元硬币——这种情况下贪心失效必须用DP枚举所有组合。把这个例子讲给面试官听比干背定义有说服力得多。3. 面试常考的三类经典DP模型拆解3.1 爬楼梯与斐波那契最简单的入门模型爬楼梯问题LeetCode 70是DP入门的必修题也是高频面试题。题目描述很简单每次可以爬1级或2级台阶爬到楼顶有多少种不同的方法状态定义非常直接dp[i]表示爬到第i级台阶的方法数。转移方程就是dp[i] dp[i-1] dp[i-2]因为到达第i级台阶只能从第i-1级跨一步或者从第i-2级跨两步。初始化dp[0] 1原地不动算一种方法dp[1] 1。这个题虽然简单但面试官往往会做几个变体考察如果每次可以爬1、2、3级呢转移方程变成dp[i] dp[i-1] dp[i-2] dp[i-3]。如果相邻两步不能走相同的步数呢这就得把状态扩展成二维dp[i][j]表示到达第i级台阶最后一步走了j级的方法数。如果不只是问方法数而是要求输出所有走法呢那就得用回溯了因为DP只适合求“计数”或“最值”不适合穷举所有具体方案。注意这个题的数值会增长得很快所以通常要对结果取模比如10^97。很多候选人在这里翻车不是因为思路不对而是忘了取模导致溢出。我在面试中见过好几个人在最后一步栽在这个细节上十分可惜。def climbStairs(n: int) - int: if n 2: return n dp [0] * (n 1) dp[0], dp[1] 1, 1 for i in range(2, n 1): dp[i] dp[i - 1] dp[i - 2] return dp[n]3.2 01背包问题面试翻车重灾区01背包是动态规划里最经典的模型也是面试中的“分水岭”题目。题目描述有N件物品和一个容量为V的背包每件物品只能用一次第i件物品的重量是w[i]价值是v[i]求背包能装下的最大价值。二维状态定义dp[i][j]表示前i件物品中选取若干件放入容量为j的背包时能获得的最大价值。对于第i件物品只有两种选择不装则dp[i][j] dp[i-1][j]装则dp[i][j] dp[i-1][j-w[i]] v[i]前提是j w[i]。所以转移方程为dp[i][j] max(dp[i-1][j], dp[i-1][j-w[i]] v[i])。这个问题的核心难点在于空间优化。观察转移方程可以发现第i行的状态只依赖第i-1行所以可以用一维数组滚动更新dp[j] max(dp[j], dp[j-w[i]] v[i])。但这里有个极其关键的细节——内层循环必须从大到小遍历容量。为什么因为dp[j-w[i]]在正序遍历时已经被当前物品更新过了用的是当前物品装了一次的结果这会导致同一件物品被重复选取变成了完全背包。而倒序遍历时dp[j-w[i]]还是上一次外层循环留下的旧值也就是还没有考虑当前物品的状态这样就保证了每件物品只用一次。这个细节我在面试中问了不下二十次能正确答出原因的候选人不到一半。def zeroOnePack(N: int, V: int, w: list, v: list) - int: dp [0] * (V 1) for i in range(N): for j in range(V, w[i] - 1, -1): # 关键倒序遍历 dp[j] max(dp[j], dp[j - w[i]] v[i]) return dp[V]背包问题的变体非常多完全背包、多重背包、分组背包、二维费用背包每种都是在基础模型上做一些改动。面试时要能快速识别题目属于哪种模型然后对应调整状态定义和遍历顺序。比如完全背包每件物品可以无限次使用遍历顺序就变成正序分组背包每组只能选一件就要加一层循环处理组内选择。这些变体不要求你全部背下来但至少要知道核心的思考方式。3.3 最长递增子序列与最长公共子序列序列型DP的代表序列型DP是面试另一大热门其中LIS最长递增子序列和LCS最长公共子序列是两道必刷题。LIS问题LeetCode 300给定一个数组求最长严格递增子序列的长度。状态定义dp[i]表示以nums[i]结尾的最长递增子序列长度。初始时每个元素自身构成一个长度为1的子序列所以dp[i] 1。转移时遍历i之前的所有j如果nums[j] nums[i]则dp[i] max(dp[i], dp[j] 1)。最后答案是所有dp[i]中的最大值而不是dp[n-1]——我见过好几个候选人栽在这里因为他们习惯性认为最后一项就是答案。def lengthOfLIS(nums: list) - int: n len(nums) dp [1] * n for i in range(n): for j in range(i): if nums[j] nums[i]: dp[i] max(dp[i], dp[j] 1) return max(dp) if n 0 else 0这里再补充一个进阶版维护一个tails数组用贪心加二分把时间复杂度从O(n^2)降到O(nlogn)。tails[k]表示长度为k1的递增子序列的最小结尾元素。遍历数组时用二分查找找到第一个大于等于当前元素的位置并更新它。这个技巧面试时属于加分项但我建议先把基本版本写对再考虑优化。LCS问题LeetCode 1143给定两个字符串text1和text2求它们的最长公共子序列长度。状态定义dp[i][j]表示text1的前i个字符和text2的前j个字符的最长公共子序列长度。转移方程分两种情况如果text1[i-1] text2[j-1]说明当前字符相等dp[i][j] dp[i-1][j-1] 1如果不等dp[i][j] max(dp[i-1][j], dp[i][j-1])边界条件dp[0][j]和dp[i][0]都为0因为空字符串和任何字符串的公共子序列都是空。思考LCS问题时代入感很重要。你可以想象成两个人各拿一个字符串从左往右扫描逐个字符比较。相等就都往前走一步并计数加一不相等就分别试一下“跳过text1的字符”和“跳过text2的字符”两种情况取较大的结果。这种从实际过程出发想问题的方式比死记转移方程有用得多。def longestCommonSubsequence(text1: str, text2: str) - int: m, n len(text1), len(text2) dp [[0] * (n 1) for _ in range(m 1)] for i in range(1, m 1): for j in range(1, n 1): if text1[i - 1] text2[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[m][n]顺带提一句编辑距离LeetCode 72是LCS思路的进阶版也是极高频面试题。它定义了三种操作插入、删除、替换求把一个字符串变成另一个字符串的最少操作次数。状态定义dp[i][j]表示word1的前i个字符变成word2的前j个字符需要的最少操作次数。重点理解三种操作对应转移方程里的哪一项——删除字符对应dp[i-1][j] 1插入字符对应dp[i][j-1] 1替换字符对应dp[i-1][j-1] 1。这个题啃下来你对DP的理解会再上一个台阶。3.4 数字三角形理解“从底向上递归”的最佳样例数字三角形是一道很好的思维进阶题。题目通常描述为给定一个三角形从顶部到底部寻找一条路径使得路径上的数字之和最大每一步只能移动到下一行中相邻的数字上。这道题的常见做法有两种自顶向下和自底向上。自顶向下的话状态定义dp[i][j]表示从顶部走到第i行第j个位置的最大路径和转移方程为dp[i][j] min(dp[i-1][j-1], dp[i-1][j]) triangle[i][j]需要注意边界位置只有一条路径可选。自底向上的做法更简洁从最后一行开始往上推dp[i][j] triangle[i][j] max(dp[i1][j], dp[i1][j1])最后答案就是dp[0][0]。实际做题时我更喜欢自底向上因为它不需要处理边界条件代码更优美。比如在LeetCode上数字三角形有很多变种从“最小路径和”到“最大路径和”思路完全一样。如果你把这道题理解了再看矩阵路径问题比如机器人从左上角走到右下角的路径数或最小代价会发现其实就是把三角形换成了矩阵思路完全一脉相承。面试中的一个常见追问是“如果让你输出具体路径怎么改”这时候就要在DP的基础上额外维护一个路径数组在每个状态转移时记录下选择的方向最后从终点倒推回起点。这个思路很重要因为很多面试官喜欢从“求最优值”升级到“求最优方案”。4. 一套可复用的DP解题流程4.1 从识别题目到写出代码的五个步骤我在刷题时总结了一套固定的流程现在分享出来。这套流程让我在面试中遇到新题时不会慌乱也推荐你试试。第一步识别题型。拿到题目先判断它是不是DP题。常见的信号包括求最值最大、最小、求方案数、求可行性能不能达到目标、数据规模在10^5以内但暴力枚举会爆炸。这些特征一出现优先往DP方向想。第二步设计状态。这是最关键的一步。问自己几个问题问题的“子问题”是什么子问题需要哪些参数来描述一维dp够不够还是需要二维甚至三维一般来说状态定义得越贴近“原问题的规模缩小的版本”就越容易推导转移方程。第三步推导转移方程。这一步的核心是“站在当前状态思考最后的动作是什么”。比如爬楼梯问题到第i级台阶的最后一步是跨1级还是2级背包问题第i件物品装还是不装LCS问题当前两个字符相等还是不相等。把这个“最后一步”想清楚转移方程就写出来了。第四步确定初始化。回到状态定义思考“最小的子问题”是什么边界条件怎么设。这一步最容易出错但也是最好检查的——用题目给的例子手动模拟几轮如果边界不对很快就会暴露。第五步确定遍历顺序并写代码。根据状态转移方程看依赖关系如果dp[i]依赖dp[i-1]从前往后遍历如果依赖dp[i1]从后往前遍历二维状态看行和列的依赖方向。遍历顺序从数学上讲是“拓扑序”简单理解就是保证算当前状态时它依赖的所有状态都已经算过。4.2 用一个完整例子走一遍流程以LeetCode 322零钱兑换为例走一遍我们这个流程。题目给定不同面额的硬币coins和一个总金额amount求凑成总金额所需的最少的硬币个数若无法凑成则返回-1。第一步识别题型求最少硬币个数是求最值问题符合DP特征。第二步设计状态dp[i]表示凑成金额i所需的最少硬币数量。这个状态定义很自然因为“凑成更小的金额”就是“凑成总金额”的子问题。第三步推导转移方程要凑成金额i最后一步一定是放了一枚面额为coin的硬币所以dp[i] min(dp[i - coin] 1) for coin in coins and coin i。注意这里枚举所有硬币这是完全背包的思想——每种硬币可以用无限次。第四步初始化dp[0] 0表示凑0元不需要任何硬币。其他dp[i]初始化为一个很大的数比如amount 1表示暂时不可达。为什么要用这么大的数因为目标是求最小值用一个大数作为“无限大”占位方便后续被更新。第五步遍历顺序和代码dp[i]依赖dp[i-coin]coin是正数所以i从小到大遍历是安全的。def coinChange(coins: list, amount: int) - int: dp [amount 1] * (amount 1) dp[0] 0 for i in range(1, amount 1): for coin in coins: if coin i: dp[i] min(dp[i], dp[i - coin] 1) return dp[amount] if dp[amount] amount else -1我们把这几道经典题放在一起对比一下面试前快速扫一眼会有帮助题目状态定义转移方程核心初始化遍历顺序爬楼梯dp[i] 到第i级的方法数dp[i] dp[i-1] dp[i-2]dp[0]1, dp[1]1从前往后01背包dp[j] 容量j下的最大价值max(dp[j], dp[j-w[i]]v[i])dp[0...V]0物品在外容量倒序LISdp[i] 以nums[i]结尾的LIS长度max(dp[j]1) where nums[j]nums[i]dp[i]1外层i内层jiLCSdp[i][j] 两前缀的LCS长度相等则1不等取maxdp[0][j]0, dp[i][0]0外层i内层j零钱兑换dp[i] 凑i元的最少硬币数min(dp[i-coin]1)dp[0]0其他为大数金额从低到高4.3 空间优化的通用套路很多DP题在写出二维状态后面试官都会追问一句“能不能优化空间”这是因为空间优化能体现你对状态转移本质的理解。最常用的优化手段是滚动数组。比如LCS的dp[i][j]只依赖dp[i-1][j]、dp[i][j-1]、dp[i-1][j-1]这三项本质上只涉及上一行和当前行所以可以用两行滚动空间从O(mn)降为O(n)。如果能再进一步观察到dp[i][j-1]就是当前行前一个格子那连第二行都能省掉只用一维数组加一个临时变量保存左上角的值。不过我要提醒一下空间优化往往会让代码变得抽象面试现场如果写不出来老老实实用二维数组也完全没问题。关键是先把功能做对再谈优化。我见过太多候选人强行优化结果在“左上角值被覆盖”这种细节上翻车反而得不偿失。另一个常见的空间优化场景是数位型DP这类题时常用到前缀和技巧。比如子数组和等于K的个数、最大子数组和等问题都用到类似“前缀和哈希表”的优化思路。本质上还是DP只是把状态存到哈希表里换取更快的查找速度。这块可以作为进阶内容补充学习但不是这篇文章的重点。5. 实操过程中我踩过的坑和排查经验5.1 状态定义错了后面全白搭我刚开始刷DP题时踩过最深的一个坑就是状态定义不够“完整”。举一个具体例子LeetCode 152乘积最大子数组。我最开始的状态定义是dp[i]表示以第i个元素结尾的最大子数组乘积。这个定义看起来合理但遇到负数就出问题了——因为当前的最大乘积可能是由之前的最小乘积乘上当前负数得到的。正确的做法是同时维护两个状态dpMax[i]表示以第i个元素结尾的最大乘积dpMin[i]表示以第i个元素结尾的最小乘积。这样当遇到负数时通过交换最大和最小就能正确处理。这个经历让我深刻体会到状态定义不能只顺着题目的表面意思走要想清楚数据之间的相互作用。排查这类问题有个实用技巧当你发现转移方程对某几个测试用例始终不对时不要急着改方程先回头检查状态定义是否覆盖了所有情况。如果状态变量不足以区分不同的子问题形态那无论怎么调转移方程都是徒劳。5.2 遍历顺序错了结果悄悄变错在讲解01背包空间优化时我强调了内层循环必须倒序遍历。这个问题的本质在于“状态依赖的时效性”一维滚动数组当前格子的值可能来自上一轮旧值也可能来自这一轮已被当前物品更新。倒序遍历保证了在用到dp[j-w[i]]时它还是上一轮的旧值从而保证每件物品只被用一次。类似的坑在完全背包里也存在只不过方向相反——完全背包需要正序遍历因为允许同一种物品多次取用。我记得有一次刷一道完全背包的变体题因为没仔细审题把正序写成了倒序结果提交后有两三个用例怎么都过不了。用调试器一看才发现问题当时就意识到遍历顺序绝不是可以随手一写的细节。排查遍历顺序问题的最好方法是打表观察。把dp数组在每一轮循环后的值打出来对照手算的期望值通常一眼就能看出是哪里的更新顺序出了问题。DP题的调试比普通题更依赖纸笔推演别偷懒。5.3 初始化值选不对答案差之千里初始化是DP里最容易被忽视、却最容易造成Bug的环节。最常见的类型是“极大值/极小值”的选取。比如零钱兑换问题如果你把dp[i]初始化成float(inf)后面做min运算就没问题但如果初始化成0那min的结果永远是0整个DP就是废的。另一种情况是边界条件的上下界。比如LCS中dp数组的维度是(m1) x (n1)多出的第0行第0列就是用来表示空字符串的情况。如果你把数组开成m x n那就没有空字符串的边界状态初始化就会无从下手后续越界也是必然。我建议在写完代码后先用题目给的示例逐行模拟一遍。这个过程虽然耗时但对发现边界问题极其有效。特别是当dp数组下标从1开始时循环里的i-1、j-1这样的偏移最容易出错手动推两轮就能查出来。5.4 判断错误这题到底能不能用DP面试中还有一种容易丢分的场景题目其实不适合用DP但你硬套DP框架。比如求全排列的所有具体方案这是典型的回溯/搜索问题DP只适合求方案数不适合枚举方案。再比如求最短路径如果图中存在负权边Dijkstra和传统的DP方法都需要调整。判断一个题能不能用DP核心看两条第一问题有没有最优子结构——即大问题的最优解能否由子问题的最优解推导出来第二子问题之间有没有重叠——如果子问题完全不重叠用递归就行了DP没有收益。如果你能快速说出这道题满足这两条再用DP做基本不会出现原则性错误。5.5 面试时写DP题的讲解顺序最后分享一个面试技巧。写DP题时不要闷头就敲代码而要边写边讲。我通常按这个顺序讲先讲状态定义是什么为什么这样定义再讲转移方程怎么来的重点说“最后一步的选择”是什么然后讲初始化为什么这么设最后提一下遍历顺序和空间复杂度。这样讲下来面试官能清楚地看到你的思路过程即使最后代码有小Bug也能通过沟通弥补。如果中途发现自己状态定义推不下去了千万别慌。直接跟面试官说“我换一个状态定义再试试。”这比死磕到底要加分得多。面试官更看重你从错误中调整思路的能力。这类情况我在实际面试中遇到过好几次有一次候选人把状态从一维改成二维后思路瞬间通了最终顺利给出了正确的转移方程虽然花的时间多一点但最后评价并不差。6. 经典DP题的进阶方向但这几道先吃透这篇文章我们聚焦在“经典动态规划1”主要覆盖了入门级的爬楼梯、背包、LIS、LCS和零钱兑换。这些题是DP的地基一定要吃透。基础打牢后你可以往几个进阶方向拓展区间DP比如戳气球、最长回文子序列、树形DP比如打家劫舍III、二叉树的最大路径和、状压DP比如旅行商问题、数位DP等等。这些题型在面试中也经常出现但通常排在基础题之后考所以先把当下的内容消化掉更为关键。我个人的建议是以这些经典题为抓手把每一道的状态定义、转移方程、初始化、遍历顺序这四要素烂熟于心再延伸到变种题上去。刷题时不要贪多一道题吃透比草草刷十道有用得多。所谓吃透就是合上答案能独立推导、能随口说出代码的每一行为什么这样写、能回答出面试官的各种追问。最后我建议每做完一道题都在笔记里写一下“这道题的状态设计对我来说是自然的还是不自然的”。如果觉得不自然说明你对这类问题的感受还不够深隔几天回来重做一遍。我的很多学生用这个办法不到一个月就对DP题形成了比较稳定的直觉。这一点对面试备考的帮助远比刷题数量要大。