又是动态规划。这话题在算法面试里真的是绕不过去的坎。每次聊到它候选人的表情大致能分成两派刷过题的人觉得套路就那几招没刷过的人直接被状态转移方程劝退。我自己面试别人的时候也发现动态规划几乎成了区分“背题型选手”和“真懂型选手”的分水岭。尤其是一到 01背包问题很多人能背出代码但一问“为什么容量要倒着遍历”就卡住了。今天这篇继续之前那个系列重点聊面试里最常考的几类经典动态规划题以 01背包问题 为主线顺带讲清楚完全背包、最长上升子序列、编辑距离这些高频考点。内容全部用 Python 实现配合我当时刷题和面试别人时踩过的坑希望对正在准备算法面试的朋友有点实际帮助。我会把重点放在“为什么这么做”上而不是只丢一份代码。动态规划这个东西代码谁都会默写关键是你能不能在面试官的连环追问下把状态定义、转移逻辑、初始化边界讲明白。这恰恰是最容易翻车的地方。1. 动态规划面试题的整体思路1.1 为什么状态定义是DP的魂动态规划的题十道里面有九道难点根本不在写代码而在定义状态。我见过太多人一上来就盯着样例试试图“看出”规律这基本是浪费时间。正确的思路是先回答一个问题我需要用什么维度来描述当前局面这里面有个经验之谈状态维度通常就是你做决策时需要考虑的几个变量。比如背包问题有两个核心变量——当前处理到第几个物品、当前背包剩余容量能用多少所以状态天然是二维的编辑距离有两个字符串所以状态就落在两个字符串的下标上最长上升子序列只有一个数组但你需要知道“以哪个位置结尾”的子序列所以一维就够了。状态定义还有一个特别容易犯的毛病定义的维度太少导致信息丢失。比如最长上升子序列你要是只把状态定义成dp[i]表示前 i 个元素中最长上升子序列的长度那转移的时候根本不知道上一个数是多少没法判断能不能接上去。正确做法是以第 i 个元素结尾这样末尾值就固定了转移时只需要往前找一个更小且更长的序列去拼接。所以面试的时候面试官如果问“你为什么要这么定义状态”你一定要能说出这个状态包含了后续转移所必需的全部信息。这句话是动态规划的魂也是你展示思维深度的机会。1.2 转移方程是怎么推出来的状态定义完了之后下一步就是推转移方程。很多人的困惑是这个方程怎么像变魔术一样就出来了其实没那么玄转移方程本质上就是在枚举“最后一步做了什么”。拿背包问题来说我处理第 i 个物品时最后一步的决策只有两个放进背包或者不放进背包。不放进背包那状态就等于处理前 i-1 个物品时的最好结果放进背包那就必须满足容量放得下这个物品结果是当前物品价值加上“剩余容量”下前 i-1 个物品的最好结果。两个选择取最大值方程就写出来了。这个方法对所有 DP 都适用想清楚最后一个动作的所有可能性再把每种可能性用更小规模的子问题表示出来最后取最优或累加。我在面试别人时经常提示候选人用这种方式去推方程十有八九能推出来。反观那些背方程的一旦题目换个马甲立刻懵。另一个要点是写完方程之后一定要自己手动推导一遍确认方程在边界条件下也成立。比如背包容量为 0 时、字符串为空时状态能不能正确转移。这一步能帮你提前发现很多初始化问题省得写到一半才发现越界。2. 01背包问题二维到一维的完整演进2.1 二维DP版本先把问题建模做对01背包问题 是面试里最经典、也最常被拿来当引子的题。题目描述一般是这样的有 n 个物品每个物品有重量 w[i] 和价值 v[i]背包容量是 C每个物品最多选一次问能装下的最大价值是多少。第一次做这道题不要急着优化空间先把二维版本写对。状态定义我前面提到了dp[i][j]表示从前 i 个物品中选总重量不超过 j 时能获得的最大价值。注意这里“前 i 个物品”在代码里通常对应索引 i-1初始化时要把下标对齐否则一写就乱。转移方程分两种情况。第 i 个物品不选dp[i][j] dp[i-1][j]第 i 个物品选前提是j w[i]此时dp[i][j] dp[i-1][j-w[i]] v[i]。两个取最大值。完整代码长这样def knapsack_01(n, C, w, v): # 用 1 到 n 表示物品0 表示一个都不选 dp [[0] * (C 1) for _ in range(n 1)] for i in range(1, n 1): for j in range(C 1): # 不选第 i 个物品 dp[i][j] dp[i-1][j] # 选第 i 个物品如果能放下 if j w[i-1]: dp[i][j] max(dp[i][j], dp[i-1][j-w[i-1]] v[i-1]) return dp[n][C] n 4 C 7 w [1, 3, 4, 5] v [1, 4, 5, 7] print(knapsack_01(n, C, w, v)) # 输出 9这个版本的代码时间复杂度 O(nC)空间复杂度 O(nC)。在面试场景下大部分面试官看到你能写出二维版本就默认你具备 DP 的基础建模能力了。但接下来几乎一定会追问一句“空间能优化吗”这就进入下一节的话题。2.2 一维空间优化的关键倒序遍历一维优化的核心观察是dp[i][j]只依赖dp[i-1][...]也就是上一行的数据。那我们完全可以只保留一行实时更新空间降到 O(C)。但这里有个天大的坑如果正着遍历容量dp[j]会被本轮刚更新过的值污染导致同一个物品被选多次这就不再是 01背包了变成了无限背包。解决办法就是倒着遍历容量。因为dp[j-w[i]]在倒序时还没有被本轮更新读到的还是上一轮的数据等价于dp[i-1][j-w[i]]。def knapsack_01_1d(n, C, w, v): dp [0] * (C 1) for i in range(n): # 倒序遍历保证每个物品最多选一次 for j in range(C, w[i] - 1, -1): dp[j] max(dp[j], dp[j - w[i]] v[i]) return dp[C]我面试的时候特别喜欢问一个细节为什么内层循环范围是range(C, w[i]-1, -1)而不是range(C, -1, -1)答案很简单j w[i]时j-w[i]是负数装了之后背包容量为负没有意义跳过即可。这既是个小优化也能避免潜在的数组越界问题。另外一个常被忽略的点是一维数组初始化成 0这里隐含的语义是“背包可以不装满”。如果题目改成“恰好装满”那初始化就要把dp[0]设为 0其余设为负无穷表示这些状态初始不可达。初始化的一字之差结果天差地别这个我在下一节细说。2.3 初始化边界里的坑关于初始化我见过太多精彩的翻车现场了。最典型的就是“能装多少”和“必须刚好装满”的区别。如果题目要求“最多能装的价值”不要求刚好装满初始化全 0 就行因为任何容量下不选任何物品都是一个合法方案价值为 0。如果题目要求“用物品刚好装满背包求最大价值”那必须把dp[0]设为 0、其他位置设为负无穷。因为容量大于 0 时“什么都不装”并不满足“刚好装满”这个条件属于非法状态不能用 0 来表示。负无穷这个初始值在 Python 里我经常用float(-inf)。注意它不是整数参与运算后还是浮点数刷题网站基本不影响结果但如果你对类型有洁癖可以用-10**9只要保证任何合法价值的绝对值都远小于它就行。顺便说一句这种“最多”和“恰好”的区分不只是背包题有很多 DP 题都有。比如爬楼梯问你“到第 n 级有多少种走法”初值是dp[0]1因为什么都不走也算一种方式。面试时多花 10 秒把边界语义说清楚能让面试官对你的信任度直接上一个台阶。3. 完全背包与多重背包变体的识别技巧3.1 完全背包的转移逻辑完全背包和 01背包 的区别只有一句话每个物品可以选无限次。但就是这一句话把代码和思维路径都改变了。在二维 DP 里完全背包的转移方程不能只写“不选/选一次”因为选了一次之后还能再选。正确的写法是dp[i][j] max(dp[i-1][j], dp[i][j-w[i]] v[i])。注意第二个状态从dp[i-1][j-w[i]]变成了dp[i][j-w[i]]意思是“既然已经允许无限次选第 i 个物品那我选了它之后还可以继续从第 i 个物品的状态转移过来”。如果用一维数组你会发现一个有趣的现象完全背包恰恰需要正序遍历容量。因为正序会让dp[j-w[i]]在更新时已经是本轮的“可以重复选”的状态正好符合无限次取用的语义。def unbounded_knapsack(n, C, w, v): dp [0] * (C 1) for i in range(n): for j in range(w[i], C 1): # 正序遍历 dp[j] max(dp[j], dp[j - w[i]] v[i]) return dp[C]很多人会把 01背包 和完全背包的遍历顺序搞混我自己初学的时候也栽过。后来找到一个不容易忘的记忆点01背包 的物品是“一次性”的所以更新时要从后往前避免覆盖还没用过的旧状态完全背包的物品是“无限量”的所以从前往后刷正好可以反复用同一个物品。面试时把这个逻辑讲出来比单纯说“01倒序、完全正序”要有说服力得多。3.2 多重背包的二进制拆分多重背包比完全背包更贴近现实每个物品不是无限个也不是只有一个而是有一个数量上限k[i]。面试中考多重背包的概率不算特别高但一旦考到很多人直接懵因为直接加一层数量循环会变成 O(nCk)很容易超时。解法是把 k 个相同的物品用二进制拆分成若干组每组当成一个新的 01背包 物品。比如一个物品有 7 个我可以拆成 1、2、4这三组能组合出 0 到 7 的任意数量。这个技巧来自“用 1、2、4... 可以表示任意不超过其和的整数”的二进制性质代码实现也很短def multiple_knapsack(n, C, w, v, k): dp [0] * (C 1) for i in range(n): # 二进制拆分 cnt k[i] power 1 while cnt 0: num min(power, cnt) weight w[i] * num value v[i] * num for j in range(C, weight - 1, -1): dp[j] max(dp[j], dp[j - weight] value) cnt - num power 1 return dp[C]面试时要是时间不够多重背包你不用写完整代码把“二进制拆分”这个思路讲出来面试官基本就满意了。它考察的是你懂不懂将一个看似复杂的模型转化成已知模型的能力这在工程问题里其实特别常见。4. 线性DP最长上升子序列4.1 O(n^2)解法是基础最长上升子序列Longest Increasing SubsequenceLIS也是面试常客。它跟背包结构完全不一样但 DP 的思考方式是一样的。状态定义dp[i]表示以第 i 个元素结尾的最长上升子序列长度。为什么一定“以 i 结尾”因为子序列的延续依赖最后一个元素的值不以它为结尾转移时不知道下一个数能不能接上。转移方程dp[i] max(dp[j] 1)其中j i且nums[j] nums[i]。如果前面没有比它小的那它自己就是长度为 1 的子序列。def length_of_lis(nums): n len(nums) if not nums: return 0 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)这个版本时间复杂度 O(n^2)。面试时先写出这个版本然后主动说一句“这题可以用贪心加二分优化到 O(n log n)。”很多面试官会顺着你的话让你继续写。4.2 贪心加二分的优化优化思路很巧妙维护一个数组tails其中tails[k]表示长度为 k1 的上升子序列中末尾元素的最小值。tails是单调递增的所以可以用二分查找。遍历nums时对于每个数 x在tails里找第一个大于等于 x 的位置把它替换成 x。如果 x 比tails里所有数都大就 append 到末尾。最后的len(tails)就是最长上升子序列的长度。import bisect def length_of_lis_on_log(nums): tails [] for x in nums: idx bisect.bisect_left(tails, x) if idx len(tails): tails.append(x) else: tails[idx] x return len(tails)这个优化的理解难度稍高但面试时讲清楚“末尾元素越小越有利于后面接更长的序列”这个贪心思想然后配合二分写代码基本就是满分回答了。我提醒一句这里求的是长度不是具体序列如果面试官问“怎么输出序列”就要额外开一个数组记录前驱复杂度会回到 O(n log n) 但代码更绕。5. 字符串DP编辑距离5.1 状态定义与转移编辑距离也是动态规划里的老牌经典题。题目让你计算把一个字符串 word1 变成 word2 的最少操作次数操作包括插入一个字符、删除一个字符、替换一个字符。状态定义是明摆着的dp[i][j]表示 word1 的前 i 个字符变成 word2 的前 j 个字符需要的最少操作数。转移时看 word1[i-1] 和 word2[j-1] 是否相等相等dp[i][j] dp[i-1][j-1]不相等取三种操作的最小值删除对应dp[i-1][j] 1插入对应dp[i][j-1] 1替换对应dp[i-1][j-1] 1。def min_distance(word1, word2): m, n len(word1), len(word2) dp [[0] * (n 1) for _ in range(m 1)] # 初始化从空串到 word2 需要插入 n 次 for j in range(n 1): dp[0][j] j # 从 word1 到空串需要删除 m 次 for i in range(m 1): dp[i][0] i for i in range(1, m 1): for j in range(1, n 1): if word1[i-1] word2[j-1]: dp[i][j] dp[i-1][j-1] else: dp[i][j] min( dp[i-1][j] 1, # 删除 word1[i-1] dp[i][j-1] 1, # 在 word1 中插入一个字符 dp[i-1][j-1] 1 # 替换 word1[i-1] ) return dp[m][n]边界初始化很多人会漏。dp[0][j] j表示“空串变成 word2 的前 j 个字符只能靠插入”dp[i][0] i表示“word1 的前 i 个字符变成空串只能靠删除”。这是整道题最容易出错的地方面试时一定要提一嘴。5.2 面试中的空间优化提问编辑距离这题二维版本已经能过绝大多数面试。但如果你运气不好面试官可能顺口问一句“空间能优化吗”这时你可以说由于dp[i][j]只依赖dp[i-1][j]、dp[i][j-1]、dp[i-1][j-1]三格所以可以只用两行滚动数组甚至一行加一个额外变量。一行数组的写法有点微妙因为dp[i][j-1]是当前行的左侧值而dp[i-1][j-1]是上一行的左上角值需要用一个变量临时保存。我建议面试时写两行滚动数组就好逻辑清晰又不容易出错。另外编辑距离这类问题还有不少变形比如“只允许插入和删除不允许替换”那转移就少一个分支再比如“求公共子序列”的 LCS。其实 LCS 的 DP 写法跟编辑距离很像只是转移方程变成相等时加 1不相等时取上或左的最大值。理解了编辑距离LCS 几乎白送。6. 面试现场的高频变体与临场应对6.1 背包问题的变形面试官不会总按原题出牌更多时候是把原题包装一下。比如“给定一个数组问能不能分成两个和相等的子集”本质上就是 01背包 的变体把问题转换成“能不能选出一些数使其和等于总和的一半”。这时候dp[j]就不是存最大价值了而是存布尔值表示“能不能凑出和为 j 的组合”。def can_partition(nums): total sum(nums) if total % 2 ! 0: return False target total // 2 dp [False] * (target 1) dp[0] True for num in nums: for j in range(target, num - 1, -1): if dp[j - num]: dp[j] True return dp[target]类似的变形还有“零钱兑换”完全背包求最少硬币数、“目标和”加减组合问题、“单词拆分”等等。其实它们骨子里都是背包思想只是状态含义从“能装多大价值”变成了“能不能拼出某个目标值”。我的经验是面试看到一个数组 一个目标值 每个数取不取优先往背包方向想看到一个数可以用无数次就往完全背包方向想。这个思维短路往往能帮你快速锁定正确的状态定义。6.2 遇到没见过的题怎么办面试时最怕的不是题难而是题目没见过心理先崩。我自己面试别人时其实并不期待候选人看到原题立刻秒解更看重的是遇到新题时的思考路径。我的建议是先大声说出状态定义的候选方案哪怕不完善也没关系。比如“这道题我觉得可以把状态定义成 dp[i][j] 表示前 i 个元素中满足某种条件的最优结果”然后一步一步验证是否满足最优子结构和无后效性。面试官通常会引导你纠正这个互动过程本身就是得分点。还有实在推不出转移方程的时候可以先写暴力递归再加记忆化搜索。记忆化搜索能把暴力的指数级复杂度降到多项式级而且它和 DP 本质上是一回事。很多面试官看到你能写出记忆化搜索再引导你改成迭代 DP你依然能拿到不错的评价。7. 常见问题与排查技巧7.1 状态转移方向反了刷 DP 题时最常遇到的 bug 就是遍历方向弄反。01背包 要倒序完全背包要正序爬楼梯这种一维 DP 是从小到大推。一旦方向反了结果要么错得离谱要么在个别测试用例上碰巧对非常误导人。如果发现输出不对第一件事就是检查内层循环的方向。尤其在面试现场我会先口头跟面试官确认当前是 01背包 还是完全背包这个题的状态依赖的是上一行还是当前行确认清楚再动手改。7.2 边界条件没想清楚另一个高频 bug 是下标越界。比如一维背包里dp[j-w[i]]忘了判断j w[i]二维 DP 里想用dp[i-1]却漏了i0的初始化编辑距离里忘了初始化第一行第一列。这些错误跑起来要么直接报 IndexError要么返回一个看起来合理但实际错误的结果。我处理这类问题的习惯是先写一个极小的测试用例比如 n1、C1手动跑一遍循环看看初始化和关键位置有没有被正确更新。大多数边界 bug 在这么小的例子里会立刻暴露。7.3 变量名与语义不一致最后一个经验之谈是写 DP 时变量名一定要跟状态定义对应起来。比如状态定义是“前 i 个物品”代码里就用i表示物品数量而不是下标数组取值时再用i-1取当前元素。很多人为了写起来方便把i同时既当数量又当下标结果一两行后就乱了。我个人的习惯是定义状态时在注释里明确写下“dp[i] 表示 XXXi 表示 XXX”然后代码严格按这个注释写。面试现场虽然不用写注释但自己在草稿纸上写清楚能极大减少低级失误。7.4 一些面试实战心得刷了这么多年题又被面试官面过、自己也面过别人我越来越觉得动态规划不是一个靠记忆就能应付的题型。它的核心是你是否真的理解了“状态”和“转移”这两个词。你不需要背下所有题的解但一定要能把一道新题拆成“这道题的状态是什么、最后一步有哪些选择、边界在哪”这三个问题。如果你正在准备面试建议每道 DP 题都按这个流程过一遍先自己推状态定义和转移方程再动手写代码再想一个反例验证自己的方程最后试着把空间复杂度优化一档。这四步走完一道题才算真正吃透。尤其是 01背包问题一定要做到能给一个完全没接触过的人讲明白才算合格。这个系列后面的文章我还会继续补充更多动态规划的经典题型和面试变形。如果你在刷题过程中遇到具体问题也欢迎带着代码和思路一起来聊很多时候把问题讲清楚答案自己就浮现了。