1. 动态规划题面试中的“分水岭”你要是去问那些参与过技术面试的候选人十有八九会告诉你动态规划是面试算法环节最让人心里没底的部分。甚至有些人一听到面试官说出“我们来看一道动态规划题”脑子就直接空白了。为什么因为链表、二叉树、哈希表这些题目多一点少一点你总能写出个暴力的版本至少不会是零分可动态规划一旦没找到状态转移方程很可能整个代码一个字都写不出来或者说写出来以后自己都没法说服自己它对。1.1 为什么面试官执念于动态规划这些年我陆续面过不少候选人也帮朋友做过模拟面试一个很直观的感受是动态规划的考察密度比数组、字符串这些基础题要高很多。面试官并不是故意为难人而是动态规划这道题能真实反映一个人的抽象能力和逻辑拆解能力。把现实问题抽象成数学问题把复杂过程拆成一个个子阶段并且要保证每个阶段的决策是最优的——这不就是工程师日常和代码打交道的核心思维方式吗你在工作中做性能优化、做缓存设计、做分布式任务调度都会遇到类似的“分阶段最优决策”问题。很多候选人背题背得很熟但换个马甲就认不出来这说明没有真正理解这类问题的共性抽象方式。面试官考察动态规划实质上是在考察你能否把一个全新问题快速映射到已知的问题框架里。1.2 动态规划并不是天才专属我遇到过不少刚开始刷题的人特别喜欢说“动态规划需要天赋代码写不出来是因为我脑子转不过来”。实际上动态规划是有明确套路的。把这道题的解题路径拆开看无非就是四个环节定义状态、写转移方程、确定初始化、确定遍历顺序。每个环节都有迹可循多做过几轮之后你会发现大部分面试题都是同一套骨架。这套骨架先记住一句话动态规划是一种以空间换时间的策略。我们用一个数组dp表记录子问题的解再通过这些子问题的解推导出更大问题的解。听起来很抽象但后面我们会用几个具体的例子把它拆到不能再碎你照着步骤推基本不会迷路。如果你正在准备技术面试或者觉得自己对动态规划“看到知道解法自己写却总差一步”这篇文章就是专门写给你的。下面我会用面试里最高频的几道经典题展开配完整的Python代码和解法思路把动态规划的底层逻辑和面试现场的应对策略一次性讲透。2. 动态规划四步法从定义到AC的完整链路很多博客一上来就甩状态转移方程然后说“显然可得”这对新手来说是很大的打击。动态规划本身不难难的是没人告诉你这个方程到底是怎么想出来的。所以这一章我们先把方法论建立起来后面的题全部套这个框架走。2.1 第一步状态定义一切的地基状态定义简单说就是搞清楚dp数组里每个格子存的是什么。这是整个动态规划最重要的一步也是决定后面顺不顺畅的关键。面试中最常见的动态规划题状态定义无非就是这几种一维dp[i]通常表示“前i个元素/第i个位置的最优解”比如斐波那契数列的第i项、爬到第i阶楼梯的方法数。二维dp[i][j]通常表示“前i个元素中选j个”“在i×j的网格中到达(i, j)的最优路径”等比如不同路径、01背包。状态压缩dp[mask]用二进制表示某个集合的选取状态这类题面试中稍少但部分大厂会考。状态定义怎么选有一个非常实用的小技巧先想暴力枚举时你在枚举什么变量把那个变量直接当成状态维度。举个例子爬楼梯问题暴力枚举时你在枚举“现在站在第几级台阶”那状态维度自然就是“第几级台阶”也就是dp[i]表示走到第i级台阶的方法数。再看“不同路径”问题暴力枚举时你在枚举“当前格子坐标(i,j)”那状态自然就是dp[i][j]。就这么简单。2.2 第二步状态转移方程整个题的灵魂状态定义解决“dp[i]是什么”状态转移方程解决“dp[i]从哪来”。这个方程本质上是在回答一个问题当前这个状态可以由哪些更小的状态推导出来以爬楼梯为例你走到第i级台阶只能从第i-1级迈一步上来或者从第i-2级迈两步上来。所以dp[i] dp[i - 1] dp[i - 2]这就是状态转移方程。注意这里的加号不是随便加的。因为“从i-1过来”和“从i-2过来”是两种不同的情况它们是互斥的所以把两种情况的方案数相加——这对应的是计数问题里的加法原理。如果是求最大值/最小值的问题转移方程里通常是max()或min()来套比如后面会说的打家劫舍和零钱兑换。判断用加法还是用min/max是面试中很容易被问到的点这个点你得能说清楚“为什么”。2.3 第三步初始化与边界条件最容易被扣分的地方初始化是动态规划里最冤的扣分点。方程写对了初始化错了结果全错。而且很多人在本地测试几个用例通过了但是面试官换个大一点的用例就崩了。初始化到底怎么定只要想清楚一件事最小的那个子问题它能不能直接用状态转移方程算出来还是爬楼梯转移方程是dp[i] dp[i-1] dp[i-2]那dp[0]和dp[1]能套这个公式吗不能因为dp[-1]和dp[-2]是非法索引。所以dp[0]和dp[1]必须手动给定。有了它们dp[2]、dp[3]才能依次推出来。初始化没想清楚的表现主要有两种一种是dp数组越界一种是结果差了一两个数。比如爬楼梯题目里有些人的dp[0]1dp[1]1另一些人dp[0]1dp[1]2。这取决于你定义dp[0]是“第0阶”还是“第1阶”。所以记住初始化必须严格和状态定义保持一致定义写的是“前i个”初始化就得按“前0个”、“前1个”来。2.4 第四步遍历顺序自底向上的推进逻辑遍历顺序为什么重要因为动态规划本质上是一个有向无环图你只能从已知状态推导出未知状态不能反过来更不能形成环。绝大多数入门级动态规划都是自底向上遍历也就是for循环从前往后推。但有些题需要从后往前推比如部分博弈类DP。还有些题需要先遍历物品再遍历背包或者反过来——01背包和完全背包的遍历顺序就是不一样的。这些细节背是背不牢的。我的建议是你每次写代码前自己在注释里写一句“我当前这个dp[i]依赖哪个更小的状态那个状态必须先被算出来。”只要这句话写出来了遍历顺序就不会错。3. 五道面试必考入门题逐题拆解这一章是实战环节。我挑了五道面试中出现频率极高的经典题从最基础的斐波那契到稍微需要动脑的零钱兑换每一道都按上面四步法拆解并附带完整的Python实现。先看这五道题的难度关系题目对应问题核心考点斐波那契数列一维基础DP状态定义与转移方程爬楼梯一维计数DP加法原理、边界初始化不同路径二维计数DP二维数组状态转移打家劫舍一维决策DP选与不选的决策零钱兑换一维最值DPmin的传递、初始化技巧3.1 第1题斐波那契数列动态规划的最简骨架题目求斐波那契数列的第n项f(0)0, f(1)1。这题大概是LeetCode上最简单也最经典的动态规划题很多刷题者的第一道DP就是它。虽然它可以用递归直接写但纯递归会带来大量的重复计算——这就是后面要说的“重叠子问题”概念。用四步法来分析状态定义dp[i]表示斐波那契数列的第i项状态转移dp[i] dp[i-1] dp[i-2]初始化dp[0]0, dp[1]1遍历顺序从2到n依次计算def fib(self, n): if n 0: return 0 dp [0] * (n 1) dp[0] 0 dp[1] 1 for i in range(2, n 1): dp[i] dp[i - 1] dp[i - 2] return dp[n]这个最简版本能过但面试官大概率会追问能不能降低空间复杂度这题的时间复杂度是O(n)因为for循环从2跑到n空间复杂度也是O(n)因为我们开了一个长度为n1的数组。但实际上我们推第i项时只用到了前两项更早的项根本不会再被用到所以完全可以用两个变量滚动记录这就是滚动数组优化的雏形。def fib(self, n): if n 0: return 0 prev, curr 0, 1 for _ in range(2, n 1): prev, curr curr, prev curr return curr面试中如果你能主动从O(n)空间优化到O(1)空间绝对是一个加分项。3.2 第2题爬楼梯状态转移的直观感悟题目假设你要爬n阶楼梯每次可以爬1阶或2阶问有多少种不同的方法可以爬到楼顶。这可能是动态规划题里对新手最友好的一道因为它的现实含义太直观了。把它抽象成数学模型到达第i阶台阶的方法数dp[i]等于从第i-1阶跨一步加上从第i-2阶跨两步。这不就递推公式出来了def climbStairs(self, n): if n 1: return 1 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[0]初始化成1然后从i2开始遍历。这么写对不对严格说是对的但前提是你把dp[0]定义为“从起点到第0阶的方法数”且约定空台阶也算一种走法。可问题在于这种定义对面试官来说不够直观很容易在追问时把自己绕晕。我建议在面试时选择状态定义最通俗的版本也就是dp[1]1, dp[2]2这种表达更不容易引起歧义。面试官如果继续追问“能不能把空间从O(n)降到O(1)”你就按斐波那契里那种滚动变量的方式改造因为爬楼梯本质上就是一个斐波那契数列的变体只是初始值不同。3.3 第3题不同路径二维DP的起点题目一个机器人位于m×n网格的左上角每次只能向下或向右移动一步问到达右下角有多少条不同路径。二维DP和前面一维DP的最大区别是状态从一维数组变成了二维数组转移方向也从一个方向变成了两个方向。但核心思路是一样的。状态定义dp[i][j]表示从左上角走到格子(i, j)的不同路径数状态转移dp[i][j] dp[i-1][j] dp[i][j-1]初始化第一行和第一列所有格子都是1因为只能一直向右或一直向下走遍历顺序双重for循环从左上角向右下角推进def uniquePaths(self, m, n): dp [[0] * n for _ in range(m)] for i in range(m): dp[i][0] 1 for j in range(n): dp[0][j] 1 for i in range(1, m): for j in range(1, n): dp[i][j] dp[i - 1][j] dp[i][j - 1] return dp[m - 1][n - 1]在Python里写二维数组时有个常见的坑dp [[0] * n] * m这样写虽然看起来创建了m行n列的二维数组但实际每一行都是同一个对象的引用。改其中一行的某个值所有行都会跟着变这种bug很难查面试现场要是出现这种问题还是很尴尬的。所以一定要用列表推导式[[0] * n for _ in range(m)]来创建这是Python写DP题的基本功。这道题的动态规划转移逻辑也很好理解你到达(i, j)格子要么是从上方格子(i-1, j)下来的要么是从左方格子(i, j-1)过来的两种方式的路径数相加就是达到当前格子的总路径数。这里面的加法原理和爬楼梯完全一致。3.4 第4题打家劫舍状态与决策分离题目你是一个小偷沿街有一排房子每个房子里有金额不同的现金。但不能偷相邻的两间房子问最多能偷多少钱。打家劫舍比前几道题多了一层“决策”的意味对每个房子你面临的不是“能不能到”而是“偷还是不偷”。如果你不在状态里把决策表达清楚这道题会让人很纠结。状态定义dp[i]表示从第0间到第i间房子能偷到的最大金额状态转移dp[i] max(dp[i-1], dp[i-2] nums[i])初始化dp[0]nums[0]dp[1]max(nums[0], nums[1])遍历顺序从2到n-1这里转移方程的含义是对第i间房子你有两种选择——不偷那么前i间房子的最大值就是dp[i-1]偷那么第i-1间房子不能偷所以是dp[i-2]nums[i]然后取两种选择里的较大值。这个“选与不选”的思考方式会贯穿所有更复杂的动态规划问题。def rob(self, nums): 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[i]的定义是“前i间房子的最大金额”它已经把偷第i间和不偷第i间两种情况的最优值同时包含了转移方程里用max自动做了选择。这个思想可以迁移到很多决策类DP里比如股票买卖问题、跳跃游戏等。3.5 第5题零钱兑换最值的传递与剪枝题目给定不同面额的硬币coins和一个总金额amount计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额返回-1。这题比前面几道难在两点一是硬币可以无限使用属于完全背包问题二是某些金额可能无法凑出来需要特殊处理。状态定义dp[i]表示凑成金额i需要的最少硬币数状态转移dp[i] min(dp[i - coin] 1) 对所有coin遍历初始化dp[0]0其他全部初始化为一个大数如amount1表示“暂不可达”遍历顺序从1到amountdef coinChange(self, coins, amount): dp [amount 1] * (amount 1) dp[0] 0 for i in range(1, amount 1): for coin in coins: if i - coin 0: dp[i] min(dp[i], dp[i - coin] 1) return dp[amount] if dp[amount] ! amount 1 else -1这里最关键的点是初始化为什么dp数组初始化为amount1而不是一个很大的数比如99999因为你要确保后续用min判断时能覆盖“不可达”的状态而amount1是理论上的最大可能值。比如我们只有1元硬币时凑10元最多用10枚amount1就是1111肯定比任何一种合法组合要多。最后判断时如果dp[amount]还是amount1说明一直没被更新过也就是根本凑不出来返回-1。这道题的代码里有个隐藏的遍历顺序知识点内层遍历硬币的顺序无所谓因为dp[i]只依赖比自己更小的dp[i-coin]而它们在计算dp[i]之前已经全部算好了。这和01背包“为了避免重复使用物品需要逆序遍历”不一样原因就是硬币是无限量使用的——这也是完全背包和01背包在遍历顺序上的核心区别。面试时如果能主动说出这一点答完这题就给面试官留下了“这人真的懂DP”的印象。4. 面试中如何快速识别一道题该用动态规划很多人最大的问题不是不会写动态规划而是面对一道从没见过的题根本不知道它该用动态规划。等面试官提醒“这题可以用DP做”又觉得好像确实能用。所以这一章专门聊聊怎么识别DP题。4.1 三个特征判断最优子结构、重叠子问题、无后效性动态规划能解的题通常同时具备三个特征最优子结构大问题的最优解可以由子问题的最优解组合而成。举一个反例就明白了——如果你要找一个班的最高个学生这可以拆成“找每个小组的最高个”然后取全体最大值但如果你要找“班里身高排第二的学生”你就不能简单说“找每个小组第二高的然后选最值”——因为全班第二高可能只是某个小组的第一名这种问题不具备最优子结构。重叠子问题不同的大问题会依赖相同的子问题。举个对比二分查找没有重叠子问题因为每次递归都切掉了问题空间的一半左右两边是不同的子问题而斐波那契数列里fib(5)要算fib(4)和fib(3)fib(4)又会算fib(3)这个fib(3)被重复计算了这就是重叠子问题。出现重叠子问题是“要不要用动态规划”的第二个信号。无后效性某个状态一旦确定之后的过程不会影响之前的状态。打家劫舍里当你面对第i间房子做决策时你不需要知道第i-1间房子“当时是怎么决策的”只需要知道前i-1间房子的最大金额这个数值就够了。如果某个问题是“有后效”的动态规划就会失效得换思路。在面试现场我会在看完题目后在草稿纸上快速对照这三个特征当场判断是否往DP方向想。这个过程虽然只有十几秒但对稳定心态、确定思路方向帮助非常大。4.2 暴力搜索是动态规划的第一版草稿如果你实在看不出状态转移方程还有一条兜底路径先写一个暴力深度优先搜索(DFS)再从暴力解法中提炼记忆化搜索最后把记忆化搜索改写成递推式动态规划。还是举爬楼梯的例子。最容易想到的暴力方法是递归def climbStairs(self, n): if n 1: return 1 if n 2: return 2 return self.climbStairs(n - 1) self.climbStairs(n - 2)这段代码是对的但效率极低因为大量子问题被重复计算。这时候加一个缓存字典就是记忆化搜索def climbStairs(self, n): memo {} def dfs(i): if i 1: return 1 if i 2: return 2 if i in memo: return memo[i] memo[i] dfs(i - 1) dfs(i - 2) return memo[i] return dfs(n)而你会发现记忆化搜索的递归方向是“自顶向下”把memo数组改成dp数组、把递归改成循环就得到了标准的自底向上动态规划。对新手来说从暴力DFS到记忆化搜索再到递推DP是一条非常友好的学习曲线。面试时如果一时卡壳跟面试官说“我先从暴力搜索的角度理一下思路”不会让人觉得你不行反而让人觉得你解决问题有章法。5. 动态规划的代码优化滚动数组的降维打击面试里动态规划题答完基础版本之后面试官最常见的追问就是“空间复杂度能不能优化到O(1)”或“能不能省掉一维”。省空间的核心思想很简单当前的dp值只依赖于前面某几个状态那些永远不会再被用到的状态就没必要继续存着。这就是滚动数组的核心思想。咱还是用爬楼梯举个特别直观的例子def climbStairs(self, n): if n 1: return 1 if n 2: return 2 a, b 1, 2 for i in range(3, n 1): a, b b, a b return b这里a保存着dp[i-2]b保存着dp[i-1]。每推进一个循环a前进到b的位置b更新为新算出的dp[i]。因为第i个状态只依赖前两个状态所以整个数组被压缩成两个变量空间复杂度从O(n)降到O(1)。这招对斐波那契、爬楼梯这类“只依赖前两个状态”的题百试百灵。对于二维DP题比如“不同路径”也可以做类似的空间压缩因为dp[i][j]只依赖dp[i-1][j]上一行和dp[i][j-1]当前行的左边一个所以不需要保留整个二维表只需要保留一行就行。一行数组在遍历过程中不断更新左边的值就是旧的dp[i][j-1]更新后的值也就是新算出来的值更新前它存的是dp[i][j-1]更新后变成dp[i][j]。这就是“用当前行的左边一个值代替二维状态里的左边格”的原理。不过我要提醒一句空间压缩版本虽然代码更短但在面试中直接写压缩版本有时候反而会让面试官觉得你在炫技或者很难follow你的思路。我个人的习惯是先把二维DP完整版本写好跟面试官说明白状态和转移再主动提出“可以优化到一维”然后写出优化的版本。这样既展示了基本功又展示了优化意识加分最明显。6. 面试实战动态规划题的标准答题流程与避坑清单最后一个环节我们把整套方法论收拢成一套面试现场可以直接照做的操作流程。很多候选人不是不会解题而是解题的过程太乱东一榔头西一棒子给面试官留下了思维不清晰的印象。按照固定流程走至少你能保证自己在面试高压环境下不乱。6.1 标准答题流程照着做就不会翻车第一步读题并确认状态定义。先别急着写代码跟面试官说“我先把dp[i]定义为...”说清楚每个下标代表什么。这一步可能在15秒内完成但它决定了整个解题方向。第二步写出状态转移方程。在注释里把方程写出来并用一句话解释“当前状态可以由哪几个小状态推导而来”。这一步是给面试官看的也是给自己理思路的。第三步明确初始化。单独用注释标出dp[0]和dp[1]等边界值是怎么定的以及为什么这么定。第四步确定遍历顺序。说一句“从前往后遍历因为每个状态依赖前面的状态”然后写for循环。第五步运行一个小样例。拿一个最简单的输入在脑内走一遍确认结果正确。第六步分析复杂度。主动报出时间和空间复杂度如果空间复杂度不是最优主动说明优化方案。这套流程走下来哪怕题目最后没完全答出来面试官对你的评价也不会差到哪里去。因为算法面试考察的并不是“你背过多少题”而是你在遇到没见过的题时能不能有条理地思考。6.2 动态规划现场的高频扣分点我在模拟面试里已经不知道看过多少候选人栽在下面这几个地方了扣分点一初始化错误。比如零钱兑换那道题很多人把dp[0]搞成1或者把其他初始值设成0结果整个数组全是0答案当然不对。初始化一定要跟状态定义对齐写完问自己一句dp[0]到底是什么这个值有现实含义吗扣分点二遍历方向搞反。比如某些题目依赖的是后方的状态你却从前往后推算出来的全是错的。判断遍历方向的标准很简单你依赖的dp[j]是不是已经算好了如果是说明方向对如果不是方向就错了。扣分点三Python二维数组用乘法创建。这个前面提过[[0] * n] * m是Python新手最经典的坑。原理解释一下[0] * n生成一个包含n个0的列表这一步没问题但外层再用* m时创建的是m个指向同一个列表对象的引用。也就是说你改了dp[0][0] 1你会发现dp[1][0]也变成了1因为它们是同一个对象。这个坑一旦踩到排查起来非常浪费时间。扣分点四不检查边界条件。很多题目要处理n0、n1这种特例。写代码时先写一行if防御虽然看起来多了一两行代码但能避免面试官拿边界用例把你的代码问倒。扣分点五说不清状态转移方程的含义。有些候选人代码写的飞起但面试官问他为什么dp[i]要等于dp[i-1]dp[i-2]他却支支吾吾。这等于告诉面试官你背过这道题。所以每次写完转移方程我都会在心里默念一遍“这个方程的含义是当前状态要么从上一个状态来要么从上上个状态来两条路径相加/取最值”。6.3 经典DP题的练习路径建议如果你现在刚开始准备动态规划我不建议直接刷困难题也不建议漫无目的地每天做一道。我建议按下面这个顺序分模块练第一周线性DP基础。把斐波那契、爬楼梯、打家劫舍、最大子数组和这几道题吃透重点是理解一维状态定义和转移方程的推导过程。第二周二维DP与网格问题。做不同路径、不同路径II、最小路径和。这周目标是把二维DP的表格推演彻底搞明白建议在纸上手动画一画dp表的变化过程这对理解“每个格子怎么填”特别有帮助。第三周背包问题体系。从01背包开始做分割等和子集、目标和然后过渡到完全背包做零钱兑换、完全平方数。背包问题是动态规划题里最大的家族面试中出现的频率非常高。第四周序列DP与编辑距离。做最长递增子序列、最长公共子序列、编辑距离。这组题的特点是“两个序列匹配”状态通常是二维的转移方程稍微复杂但对思维提升特别大。一个月之后你再回头看这五道基础题会发现它们已经变成肌肉记忆了。这时候再进入困难模式比如股票买卖系列、区间DP、状态压缩DP你会有一种“原来动态规划就这几种套路”的豁然开朗感。说到底动态规划是面试里少有的“投入产出比”特别高的板块。它的题目类型有边界解法套路有章法不像某些冷门知识点背了也没用。只要掌握住状态定义、转移方程、初始化、遍历顺序这四步再配套练熟二十来道经典题面试时遇到动态规划题就完全有底气了。我在实际辅导面试时最喜欢跟候选人说的一句话是动态规划不是智力题它是手艺活。手艺活靠什么靠多做多推多复盘。每次写完一道DP题都回头想想为什么状态要这么定义为什么这个题不能用贪心为什么遍历要这么走想清楚这三问比你盲目刷五十道题都管用。希望这篇梳理能帮你在动态规划这条路上省一些力气把它从“拦路虎”变成“送分题”。