2018年前后那波面试季我把力扣上动态规划的高频题翻来覆去刷了三遍最后总结下来就一句话动态规划这块面试官真不是要你背题而是想看你在几分钟内能不能把一个问题拆成子问题再把子问题串成递推关系。很多候选人挂在DP上不是因为代码写得少而是从一开始就没想清楚“状态是什么、转移靠什么、边界在哪里”这三件事。这篇文章就围绕力扣当年高频的动态规划题把这类题的底层思路、实战写法、踩坑点全部拆开讲清楚。如果你是正在准备算法面试的开发者或者刚学动态规划但总觉得自己“看题会、写题废”那这篇文章就是冲着这两个问题来的。我会把状态定义、转移方程、初始化和遍历顺序这些核心环节一个个掰开配上可以直接拿去练的代码最后再分享排查问题的实战经验。1. 动态规划成为面试考点的深层逻辑1.1 面试官到底在看什么先说一个很多人都没意识到的事实动态规划是少数几个能在一次代码面试里同时考察“理解能力、抽象能力、边界意识”的题型。链表、二叉树这类题背过模板就能应付一大半但DP题不一样它没有固定的代码骨架每道题的状态定义都可能不同面试官能直接从你的思路里看出你是在“解决问题”还是在“背答案”。我印象很深的一次模拟面试里某候选人面对一道非常经典的一维DP题上来就把dp数组开好、循环写对代码一气呵成。但面试官追问了一句“为什么这个转移方程成立如果数组元素全为负数你的边界条件还对吗”候选人一下子愣住了。这就是动态规划题最典型的特点——代码本身可能只有十几行真正值钱的是背后的推导过程。面试官通过DP题想验证的核心能力有三块第一你能不能把一个大问题分解成可复用的小问题这反映的是建模能力第二你能不能写出清晰的递推关系并解释其正确性这反映的是逻辑表达能力第三你能不能把边界条件、数组越界、空间优化这些细节处理好这反映的是工程意识。2018年那批高频题之所以反复出现就是因为它们恰好把这三点都覆盖到了。1.2 三个绕不开的核心特征学习动态规划先绕开“套路”两个字回到本质。动态规划能解决的问题有三个共同特征。第一个叫最优子结构。意思是整个问题的最优解一定由子问题的最优解构成。拿爬楼梯来说到第10级台阶的方法数一定等于到第9级的方法数加上到第8级的方法数因为最后一步要么跨一级、要么跨两级。如果一个问题不具备这种“大问题依赖小问题最优解”的结构那动态规划就不适用。第二个叫重叠子问题。举个例子用递归去算斐波那契数列第50项你会发现f(48)被算了无数遍这就是重叠子问题。动态规划的本质就是用空间换时间把已经算过的子问题结果存起来避免重复计算。面试官经常让你对比递归和DP的复杂度差异考的其实就是这一点。第三个叫状态转移。这个概念听起来玄乎说白了就是“从一个状态到另一个状态的变化规则”。dp[i]怎么由dp[i-1]、dp[i-2]演变过来这条规则写清楚整个DP的核心就完成了一大半。很多人卡住是因为不知道“状态”这个词到底指什么。我习惯用一个类比状态就是你在解题过程中记录下来的“当前处境”。到了第i级台阶是一种处境从前i个物品里选若干放入容量为j的背包也是一种处境。dp表格里的每一格就是某个特定处境下的最优答案。1.3 高频DP题的分布规律2018年力扣高频题统计下来动态规划相关的题目大致可以归成六类一维线性DP、二维矩阵DP、字符串子序列DP、背包DP、区间DP、树形DP。从面试中的出现频率看前四类占了绝大部分。具体来说爬楼梯、打家劫舍这类一维DP是入门题但别因为它们简单就轻视——很多进阶题都是从这两个模型变化出来的。最长公共子序列、编辑距离这类二维DP是考察的重点写一次基本就能举一反三。0-1背包则是很多公司“压轴题”的雏形考察你对空间优化和遍历顺序的理解是否到位。区间DP和树形DP相对冷门一点但偶尔会出现在难度较高的面试轮次里。2. 核心细节解析与实操要点2.1 状态定义想不清楚就写不出DP我一直认为动态规划里最难的一步不是写转移方程而是定状态。状态定义错了后面的一切都是空中楼阁。定状态有一个笨但有效的方法先问自己“我关心这个问题的哪个维度”再问“这个维度取不同值时我能不能用一个数代表当前最优结果”。以爬楼梯为例关心的维度就是“台阶数”所以状态可以定义为dp[i] 到达第i级台阶的不同方法数。再看打家劫舍。一排房子每个房子有金额不能偷相邻两家问能偷到的最大金额。这个问题的维度有两个一个是“偷到第几家”另一个是“偷还是不偷”。通常我们把状态设计成dp[i] 偷到前i家时能获得的最高金额这样每一家的决策就被压缩成一个数了。状态定义有两个常见误区。第一个是把维度搞少比如计算最短编辑距离时只用一个一维数组去存结果发现转移时需要同时用到两个字符串的多个位置一维根本不够这种情况老老实实开二维。第二个是忽略了“状态代表的是最优结果而不是过程”。还是拿打家劫舍说dp[i]不会告诉你第i家到底偷没偷它只告诉你前i家的最优结果是多少——中间过程不需要保留这就是动态规划“无后效性”的精髓。2.2 转移方程推导的固定套路状态定义完成之后转移方程其实是从一个固定套路里推出来的。我把它总结成四步找最后一步、枚举决策、写出递推、验证边界。找最后一步是什么意思假设你已经知道了所有子问题的答案想从这些答案推导出当前状态。那就盯着“最后一次选择”看。爬楼梯的最后一步是“从第i-1级跨一级”或“从第i-2级跨两级”因此dp[i] dp[i-1] dp[i-2]。打家劫舍的最后一步是“第i家偷了”或“第i家没偷”如果偷了那第i-1家就不能偷所以收益是dp[i-2] nums[i]如果没偷收益就是dp[i-1]。取两者较大转移方程就出来了。这套流程背下来其实不难难的是“枚举决策”那一步要想全。编辑距离这道题对字符word1[i-1]和word2[j-1]如果相等直接沿用dp[i-1][j-1]如果不相等你有三种操作增、删、改于是要从三个候选状态里取最小值再加一。很多人在这一步漏掉“相等”的情况或者把三种操作的候选状态搞混导致答案偏大或偏小。写转移方程之前我强烈建议先在注释里用中文把“什么时候取哪个dp值”写明白再转为代码。2.3 初始化和遍历顺序细节决定成败初始化是DP题的第二大坑点。dp[0]、dp[1]怎么设不同题差别很大。爬楼梯里dp[1] 1、dp[2] 2打家劫舍里dp[0] nums[0]、dp[1] max(nums[0], nums[1])最长公共子序列里dp[i][0]和dp[0][j]都是0因为空字符串和任何字符串的最长公共子序列长度必然是0。我自己的习惯是在写出dp数组之后先不急着循环把第一行第一列或者前两个元素手动填一遍确认它们的值符合实际意义再往后推。手动填充的过程能暴露出大量边界问题比如空字符串、只有一个元素、全是负数这些情况。遍历顺序的核心原则是计算dp[i]所用到的所有状态必须在此之前已经被计算出来。一维DP通常正序遍历就够了但0-1背包如果用一维滚动数组优化容量维必须倒序遍历否则同一件物品会被重复放入多次语义就变了。这个细节我会在下一节用代码具体讲。3. 实操过程与核心环节实现3.1 爬楼梯一维DP的入门必修题题目描述很简单假设你正在爬楼梯需要n阶才能到楼顶每次可以爬1或2个台阶问有多少种不同的方法。这道题之所以经典是因为它把动态规划最核心的思维浓缩在几行代码里。先定义状态dp[i]表示到达第i阶的方法总数。最后一步要么从第i-1阶跨一阶要么从第i-2阶跨两阶所以dp[i] dp[i-1] dp[i-2]。边界条件是dp[1] 1、dp[2] 2。def climbStairs(n): 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]时间复杂度O(n)空间复杂度O(n)。但仔细观察会发现计算dp[i]只用到前两个状态完全可以用两个变量滚动更新把空间复杂度降到O(1)def climbStairs_optimized(n): if n 2: return n prev, cur 1, 2 for i in range(3, n 1): prev, cur cur, prev cur return cur面试的时候我会建议先写出用数组的版本让逻辑一目了然等面试官追问“能不能优化空间”再改成滚动变量版本。主动展示优化过程比一上来就写精简版更能体现思考深度。3.2 打家劫舍带决策的线性DP题目描述你是一个专业的小偷计划偷窃沿街的房屋。每间房内都藏有一定的现金唯一约束是相邻的房屋不能同时被偷否则会触发报警。给定一个数组nums表示每间房的金额求不触动警报的情况下能偷到的最高金额。这道题比爬楼梯多了一个维度——每间房都有“偷”和“不偷”两种选择你要在每一步做决策。定义dp[i]表示偷到前i家房屋时能获得的最高金额。对于第i家如果偷则第i-1家不能偷收益为dp[i-2] nums[i]如果不偷则收益为dp[i-1]。转移方程def rob(nums): if not nums: return 0 if len(nums) 1: return nums[0] dp [0] * len(nums) dp[0] nums[0] dp[1] max(nums[0], nums[1]) for i in range(2, len(nums)): dp[i] max(dp[i - 1], dp[i - 2] nums[i]) return dp[-1]这里有一个很值得注意的细节dp[1]为什么要取max(nums[0], nums[1])因为前两家里只能偷一家当然选金额更大的那家。但如果你写成dp[1] nums[1]当nums[0] nums[1]时结果就会出错。这种边界条件就是面试官最容易挖坑的地方。打家劫舍还有变体比如房子围成一圈首尾也是相邻的、二叉树结构等。遇到这些变体时核心思路不变只需要调整状态定义的范围或拆分成两种情况分别计算即可。3.3 最长公共子序列二维DP的模板题给定两个字符串text1和text2返回它们的最长公共子序列长度。注意子序列不要求在原字符串中连续只要保持相对顺序即可。这道题几乎可以说是二维DP的“模板题”因为很多字符串类DP都是从它演变而来的。定义dp[i][j]表示text1的前i个字符与text2的前j个字符的最长公共子序列长度。当text1[i-1] text2[j-1]时说明当前字符可以接在之前的最优解后面所以dp[i][j] dp[i-1][j-1] 1否则当前字符对不上最长公共子序列只能来自text1少一个字符或text2少一个字符的情况取dp[i-1][j]和dp[i][j-1]中的较大值。def longestCommonSubsequence(text1, text2): 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]代码本身不复杂但有两个关键点值得强调。第一dp数组的尺寸是(m1)x(n1)而不是m x n因为我们要留出“空字符串”这一行一列作为基准。如果不加这一行一列处理i0或j0时就会频繁越界。第二当字符相等时直接使用dp[i-1][j-1] 1而不是dp[i-1][j] 1或dp[i][j-1] 1因为dp[i-1][j-1]代表的是两个字符串都去掉最后一个字符时已经匹配好的长度这样接上当前字符才保证子序列的相对顺序没有被破坏。这道题如果面试官要求输出具体的子序列而不是长度就需要用一个额外的指针回溯dp表从右下角往左上角走。这个扩展我在面试中遇到过不止一次建议提前准备好。3.4 编辑距离字符串DP的高频代表编辑距离的经典描述是给你两个单词word1和word2你可以对word1执行插入、删除、替换三种操作每次操作计1次成本求把word1转成word2所需的最少操作次数。这道题是很多公司面试题单上的常客因为它综合考察了二维DP和“三类决策”的处理能力。定义dp[i][j]表示word1的前i个字符转成word2的前j个字符所需的最小编辑距离。转移分两种情况如果word1[i-1] word2[j-1]当前字符不用处理直接继承dp[i-1][j-1]。如果两个字符不相等有三种操作可选删除word1的当前字符对应dp[i-1][j] 1在word1中插入一个字符去匹配word2的当前字符对应dp[i][j-1] 1替换word1的当前字符对应dp[i-1][j-1] 1。取三者最小值。def minDistance(word1, word2): m, n len(word1), len(word2) dp [[0] * (n 1) for _ in range(m 1)] for i in range(m 1): dp[i][0] i for j in range(n 1): dp[0][j] j 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], dp[i][j - 1], dp[i - 1][j - 1]) 1 return dp[m][n]初始化的意义要理解透彻dp[i][0] i表示把word1的前i个字符全部删除才能变成空字符串需要i次操作dp[0][j] j表示从空字符串插入j个字符变成word2的前j个字符需要j次操作。这组初始化正好对应“只能通过插入或删除实现转换”的极端场景是整个转移方程的基石。3.5 0-1背包进阶必考的核心模型有N件物品和一个容量为W的背包每件物品有重量weight[i]和价值value[i]每种物品只有一件求能装入背包的最大总价值。0-1背包之所以经典在于它引入了“选/不选”的决策以及一维滚动数组优化时“容量倒序遍历”的巧妙设计。先写二维版本。定义dp[i][j]表示前i件物品放入容量为j的背包能获得的最大价值。对于第i件物品要么不放价值为dp[i-1][j]要么放前提是j weight[i]价值为dp[i-1][j - weight[i]] value[i]。取两者最大值。def knapsack_2d(weights, values, capacity): n len(weights) dp [[0] * (capacity 1) for _ in range(n 1)] for i in range(1, n 1): for j in range(1, capacity 1): if j weights[i - 1]: dp[i][j] max(dp[i - 1][j], dp[i - 1][j - weights[i - 1]] values[i - 1]) else: dp[i][j] dp[i - 1][j] return dp[n][capacity]二维版本的逻辑非常清晰推荐在面试中先给这个方案然后再做空间优化。优化后的版本用一维数组容量必须从大到小遍历def knapsack_1d(weights, values, capacity): dp [0] * (capacity 1) for i in range(len(weights)): for j in range(capacity, weights[i] - 1, -1): dp[j] max(dp[j], dp[j - weights[i]] values[i]) return dp[capacity]为什么要倒序因为dp[j]依赖于dp[j - weights[i]]如果正序遍历较小的容量值可能在当前物品循环中被更新过导致同一件物品被“多次放入”。倒序遍历时dp[j - weights[i]]还是上一件物品状态下的值从而保证每件物品最多选一次。这个逻辑面试官几乎必问一定要能讲清楚。3.6 从暴力递归到动态规划的递进套路前面讲的都是具体题目最后这一步我想把方法沉淀成一条可复用的路径。遇到一道新DP题我的思考顺序固定是三步。第一步先尝试写暴力递归。把问题定义成一个递归函数函数的参数就是状态的维度函数返回值就是当前状态的最优结果。不要急着开dp数组先让“递归树”长出来。比如爬楼梯暴力递归就是return climb(n-1) climb(n-2)你会发现大量子问题被重复计算。第二步加备忘录。用一个字典或二维数组存储已经算过的结果递归前先查表就叫记忆化搜索。这个版本能通过面试中大部分“时间和空间要求不那么严格”的用例而且思路最容易和面试官对齐。第三步将记忆化搜索改写成自底向上的DP。把递归函数里的每一个状态映射到dp数组的对应位置循环代替递归这就是最终的迭代版本。三步走完主观上你对状态的依赖关系已经非常清楚写转移方程时不再需要“猜”。4. 常见问题与排查技巧实录4.1 数组越界普遍存在但又最隐蔽的错误数组越界的问题是力扣DP题里最常见的运行时错误。原因很好理解dp数组的下标和输入数据下标之间往往差了一个1。比如最长公共子序列dp[i][j]对应text1的前i个字符、text2的前j个字符所以访问text1[i-1]和text2[j-1]才是对的。如果直接写text1[i]i等于m时就越界了。排查这类问题的方法很直接先在循环开头打印一下i和j对照数组长度看一眼。更系统的方法是写一个assert语句在访问字符串前强制校验index len(text)开发阶段能快速暴露问题。下线前再删掉这些断言防止影响线上性能。4.2 初始化错误dp[0]不是随便填的初始化错误往往不会让程序崩溃但会让答案差一点这类bug最恼人。我踩过的一个典型场景是编辑距离的dp[0][j]赋值。第一次写的时候我把for j in range(n 1)漏成了range(1, n 1)导致dp[0][0]和dp[0][1]都是默认值0整个第一行的后续值全部跟着错。这种问题怎么快速定位有一个很实用的技巧手动把dp表格的前两行两列写出来和程序输出对比。如果手动算出的dp[1][1]和程序结果对不上十有八九是初始化没写全。注意dp[0][0]并不是永远为0它代表两个空字符串的编辑距离在编辑距离这道题里是0但在其他题目里可能要特殊处理动手前先想清楚“空状态”的实际含义。4.3 空间优化翻车滚动数组的覆盖顺序一维滚动数组优化是DP题里的加分项但也是失分重灾区。以0-1背包为例如果容量循环正序写输出结果会比正确值偏大因为同一件物品被反复放入。这类错误在逻辑上很难一眼看穿你必须清楚当前循环里正在处理的是第几件物品、dp[j - weights[i]]代表的是“上一件物品状态”还是“当前物品状态”。我的经验是在做空间优化之前先把二维版本的表格画出来。你会发现每一行的值只依赖上一行所以可以复用同一行数组。然后想清楚如果要让dp[j - weights[i]]保持上一行的值遍历方向就必须从右往左。想明白这一点再写代码就不会出错了。面试时如果时间紧张直接用二维版本拿满分值也是可以的空间优化可以作为加分包装。4.4 高频错误速查对照表为了方便排查我把动态规划题里最常见的几类错误整理成下面这个表遇到过类似情况可以直接对照错误类型典型表现排查方向状态定义不清转移方程写不出来回到“最后一步”重新分析确认dp每个维度含义数组越界运行时报IndexError检查i-1/j-1与数组size的关系注意偏移初始化遗漏答案偏小或恒为0手动填dp前两行两列验证边界值遍历方向错结果比正确值大检查是否存在重复计算0-1背包容量需倒序状态维度少结果缺失某种情况问自己“每个决策是否都体现在状态里”转移方程漏条件相等情况未处理用中文注释列出所有可能情形逐一翻译成代码4.5 有效训练DP的方法建议最后一节聊聊训练方法。很多人刷DP题喜欢按题号顺序刷我建议换个思路按“模型”分类刷。先花两天把一维线性DP的经典题吃透再花三天做二维DP和字符串DP接着啃背包问题最后去碰区间DP和树形DP。每做完一类要能用自己的话把这类模型的共同模板讲给别人听。具体操作上每道题准备一个笔记记录四块内容状态定义、转移方程、初始化、遍历顺序。不需要写长篇大论每块一两行就行。隔一周回头重做一遍不看笔记先写代码看自己能还原多少。这个办法亲测有效远比盯着题解看十遍管用。另外强烈建议每次写完DP题主动变一个条件再解一次。比如爬楼梯改成“每次可以爬1、2或者3级”打家劫舍改成“不能偷相邻两家且环形排列”最长公共子序列改成“允许字符重复匹配”。这些变形训练能帮你把模型的适用边界摸清楚。面试时遇到原题的变形不会慌。我在实际带人准备面试的过程中发现一个普遍规律能把打家劫舍和编辑距离这两道题的思路完整讲清楚的候选人动态规划基本不会考得太差。因为这两道题恰好覆盖了“决策类DP”和“多维状态DP”两大主流方向。最后再分享一个训练时的小技巧每道题先用嘴巴把思路完整说一遍再动手写代码说清楚后再写写出来的代码往往一次通过率最高。这个方法听着简单执行起来效果非常明显值得一试。