1. 为什么递归和动态规划总是被放在一起考面试算法环节里递归和动态规划几乎是绕不开的两座山。很多人刷了几十道题看到爬楼梯能秒写递归看到最长递增子序列就卡壳看到零钱兑换直接放弃。问题不在于题刷得不够多而在于没有真正理解这两者之间的血缘关系。递归是一种自顶向下的思考方式它把大问题拆成小问题假设小问题已经解决然后拼出大问题的答案。动态规划则是自底向上的工程化手段它把递归过程中重复计算的部分用表格存起来用空间换时间。两者本质上描述的是同一个东西状态转移。递归是状态转移的自然语言动态规划是状态转移的汇编语言。我见过太多候选人面试时能写出递归版本但面试官一句能不能优化一下时间复杂度就慌了。其实从递归到动态规划有一条非常清晰的路径先写出暴力递归找到重叠子问题加上记忆化搜索再改写成自底向上的递推。这条路径走通了面试中百分之八十的动态规划题都能拿下。这篇文章会从递归的底层原理讲起逐步过渡到动态规划的核心思想再通过几道经典面试题把两者的转换过程完整演示一遍。适合正在准备面试的开发者、刚接触算法的新手以及刷题刷到瓶颈想系统梳理思路的朋友。读完之后你至少能做到看到一道新题能判断它是不是动态规划问题能写出递归解能优化成动态规划解能分析时间和空间复杂度。2. 递归的本质与常见误区2.1 递归到底在做什么递归函数的本质是一个数学归纳法的程序化表达。它包含两个部分基准情况和递归关系。基准情况是问题规模小到可以直接给出答案的情况递归关系是把当前问题归约到更小规模问题的公式。以经典的斐波那契数列为例。定义是 F(0)0F(1)1F(n)F(n-1)F(n-2)。前两行是基准情况第三行是递归关系。写成代码就是def fib(n): if n 1: return n return fib(n-1) fib(n-2)这段代码读起来几乎和数学定义一模一样这就是递归的魅力表达力极强接近人类思维。但它的代价也很明显。计算 fib(5) 的时候fib(3) 会被计算两次fib(2) 会被计算三次。随着 n 增大重复计算的次数呈指数级增长。n40 的时候函数调用次数超过三亿次普通机器要跑好几秒。2.2 递归的三个致命陷阱第一个陷阱是重复计算。上面斐波那契的例子已经说明了。重复计算是递归效率低下的头号原因也是动态规划要解决的核心问题。第二个陷阱是栈溢出。每次函数调用都会在调用栈上压入一个栈帧保存参数、局部变量和返回地址。Python 默认的递归深度限制是 1000 左右超过就会抛出 RecursionError。即使语言层面没有限制栈空间也是有限的递归太深必然崩溃。我踩过这个坑有一次写一个链表反转的递归解法测试用例的链表长度是十万直接栈溢出。后来改成迭代才通过。第三个陷阱是状态定义不清晰。很多人在写递归的时候没有想清楚这个函数的参数代表什么返回值代表什么。比如写一个求二叉树最大深度的递归函数签名是def depth(node)那它的语义应该是以 node 为根的子树的最大深度。如果语义模糊递归关系就写不对基准情况也容易漏。写递归之前先用一句话把函数的语义写下来。这句话必须包含参数是什么返回值是什么在什么情况下返回。这句话写不清楚代码一定写不对。2.3 递归的适用场景判断不是所有问题都适合用递归。适合递归的问题通常具备两个特征一是问题可以分解为结构相同的子问题二是子问题的规模比原问题小且最终能收敛到基准情况。典型的适合递归的场景包括树和图的遍历、分治算法归并排序、快速排序、回溯搜索全排列、子集、N皇后、以及具有递推关系的数学问题。不适合递归的场景包括简单的线性迭代、状态空间巨大且没有重叠子问题的问题、以及递归深度可能非常大的情况。判断标准很简单如果你画出的递归树是一棵瘦高的树每层只有一个分支那递归深度就是问题规模容易栈溢出应该考虑迭代。如果递归树是矮胖的每层有多个分支但深度不大那递归写起来很自然。如果递归树中有大量重复节点那就是动态规划的用武之地。3. 动态规划的核心思想与解题框架3.1 动态规划解决了什么问题动态规划解决的是具有重叠子问题和最优子结构的问题。重叠子问题指的是递归过程中同一个子问题被多次计算最优子结构指的是原问题的最优解可以由子问题的最优解推导出来。这两个条件缺一不可。如果没有重叠子问题那递归本身就够了加缓存没有意义。如果没有最优子结构那子问题的最优解拼不出原问题的最优解动态规划的状态转移方程就写不出来。动态规划的核心操作是用表格记录子问题的解避免重复计算。这个表格可以是一维数组、二维数组也可以是哈希表。表格的每个格子代表一个子问题的答案格子之间的递推关系就是状态转移方程。3.2 动态规划的四步解题框架我总结了一个四步框架适用于绝大多数动态规划问题。第一步定义状态。状态就是表格的索引代表什么。比如dp[i]表示前 i 个元素的最优解或者dp[i][j]表示从 i 到 j 这个区间的最优解。状态定义是动态规划中最关键也最难的一步状态定义错了后面全错。第二步写出状态转移方程。这是从已知状态推导未知状态的公式。比如dp[i] max(dp[i-1], dp[i-2] nums[i])。状态转移方程决定了代码的循环结构。第三步确定初始条件和边界。初始条件是表格中最小的那些子问题的答案边界是防止数组越界的处理。初始条件写错整个表格都会错。第四步确定遍历顺序。遍历顺序必须保证计算某个状态时它所依赖的状态已经计算完毕。比如dp[i]依赖dp[i-1]那就从小到大遍历如果dp[i]依赖dp[i1]那就从大到小遍历。这四步中第一步和第二步是核心第三步和第四步是细节。面试的时候先把状态定义和转移方程说清楚再写代码面试官会觉得你思路清晰。3.3 记忆化搜索递归到动态规划的桥梁很多人觉得递归和动态规划是两种完全不同的东西其实它们之间有一座桥记忆化搜索。记忆化搜索就是在递归的基础上加一个缓存计算过的子问题直接查缓存不再重复计算。还是斐波那契的例子加上记忆化def fib(n, memo{}): if n 1: return n if n in memo: return memo[n] memo[n] fib(n-1, memo) fib(n-2, memo) return memo[n]这段代码的时间复杂度从 O(2^n) 降到了 O(n)空间复杂度是 O(n)。它保留了递归的自顶向下思维同时消除了重复计算。对于很多问题记忆化搜索已经足够通过面试而且写起来比自底向上的动态规划更直观。记忆化搜索和自底向上动态规划的区别在于记忆化搜索是需要哪个子问题的解就算哪个自底向上是把所有子问题都算一遍。前者在某些情况下更高效不需要计算所有子问题后者在某些情况下更高效没有递归调用开销。面试中两种都可以写但自底向上的写法通常更受青睐因为它没有栈溢出的风险。4. 从递归到动态规划的完整转换实战4.1 爬楼梯问题最简单的转换演示爬楼梯问题是动态规划的入门题每次可以爬 1 阶或 2 阶问爬到第 n 阶有多少种方法。先用递归写。定义climb(n)为爬到第 n 阶的方法数。最后一步要么从 n-1 阶爬 1 阶上来要么从 n-2 阶爬 2 阶上来。所以climb(n) climb(n-1) climb(n-2)。基准情况是climb(0)1climb(1)1。def climb(n): if n 1: return 1 return climb(n-1) climb(n-2)这个递归树和斐波那契一模一样有大量重复计算。加上记忆化def climb(n, memo{}): if n 1: return 1 if n in memo: return memo[n] memo[n] climb(n-1, memo) climb(n-2, memo) return memo[n]再改成自底向上def climb(n): if n 1: return 1 dp [0] * (n 1) dp[0] 1 dp[1] 1 for i in range(2, n 1): dp[i] dp[i-1] dp[i-2] return dp[n]进一步优化空间发现dp[i]只依赖前两个状态所以可以用两个变量滚动def climb(n): if n 1: return 1 prev, curr 1, 1 for i in range(2, n 1): prev, curr curr, prev curr return curr从递归到记忆化到自底向上到空间优化这是动态规划问题的标准优化路径。面试的时候如果你能把这四个版本都写出来面试官基本会认可你的功底。4.2 零钱兑换状态定义决定成败零钱兑换问题给定不同面额的硬币和一个总金额问凑出总金额所需的最少硬币数。如果凑不出返回 -1。这道题的状态定义很关键。如果定义dp[i]为凑出金额 i 所需的最少硬币数那状态转移方程是dp[i] min(dp[i-coin] 1)其中 coin 遍历所有硬币面额。初始条件dp[0]0其他dp[i]infinity。def coinChange(coins, amount): dp [float(inf)] * (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] ! float(inf) else -1如果用递归写定义minCoins(amount)为凑出 amount 所需的最少硬币数。那minCoins(amount) min(minCoins(amount-coin) 1)。基准情况是minCoins(0)0minCoins(负数)infinity。def coinChange(coins, amount, memo{}): if amount 0: return 0 if amount 0: return float(inf) if amount in memo: return memo[amount] res float(inf) for coin in coins: res min(res, coinChange(coins, amount - coin, memo) 1) memo[amount] res return res对比两个版本递归版本更直观地表达了枚举最后一枚硬币的思路动态规划版本则是把这个思路反过来从 0 开始逐步构建到 amount。两者的状态转移本质相同只是方向不同。零钱兑换有一个容易踩的坑dp[i]的初始值必须是一个不可能的大数不能是 0。如果初始值是 0那min操作永远会选 0结果全错。我见过好几个候选人在这里翻车。4.3 最长递增子序列两种状态定义的对比最长递增子序列LIS问题给定一个数组求最长递增子序列的长度。注意子序列不要求连续。这道题有两种动态规划的状态定义。第一种dp[i]表示以 nums[i] 结尾的最长递增子序列长度。状态转移方程是dp[i] max(dp[j] 1)其中 j i 且 nums[j] nums[i]。答案是max(dp)。def lengthOfLIS(nums): if not nums: return 0 dp [1] * len(nums) for i in range(1, len(nums)): for j in range(i): if nums[j] nums[i]: dp[i] max(dp[i], dp[j] 1) return max(dp)第二种定义dp[i]表示长度为 i 的递增子序列的最小结尾元素。这个定义更巧妙可以用二分查找优化到 O(n log n)。但理解起来更难面试中如果想不到用第一种 O(n^2) 的解法也足够。从递归的角度看LIS 的递归定义是LIS(i)表示以 nums[i] 结尾的最长递增子序列长度那LIS(i) max(LIS(j) 1)其中 j i 且 nums[j] nums[i]。基准情况是LIS(0)1。这个递归和动态规划的状态定义完全对应。4.4 二维动态规划编辑距离编辑距离问题给定两个字符串求把第一个字符串转换成第二个字符串所需的最少操作次数。操作包括插入、删除、替换。状态定义dp[i][j]表示把 word1 的前 i 个字符转换成 word2 的前 j 个字符所需的最少操作次数。状态转移方程分两种情况如果word1[i-1] word2[j-1]那dp[i][j] dp[i-1][j-1]否则dp[i][j] min(dp[i-1][j], dp[i][j-1], 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]这道题的递归版本是edit(i, j)表示把 word1 的前 i 个字符转换成 word2 的前 j 个字符所需的最少操作次数。递归关系和动态规划完全一样只是方向相反。二维动态规划的难点在于边界条件的初始化。dp[i][0]表示把前 i 个字符转换成空串需要删除 i 次所以是 i。dp[0][j]表示把空串转换成前 j 个字符需要插入 j 次所以是 j。这两个边界如果写错整个表格都会错。5. 面试中的高频问题与排查技巧5.1 如何判断一道题是不是动态规划面试中遇到一道新题怎么判断它是不是动态规划我总结了一个快速判断法先想递归再看递归树有没有重复节点。具体操作是尝试写出暴力递归的解法然后在纸上画出递归树。如果递归树中有大量重复节点那这道题就可以用动态规划优化。如果递归树是一棵没有重复节点的树那动态规划不适用应该考虑其他方法如贪心、分治、回溯。另一个判断依据是问题是否要求最优解或方案数。求最大值、最小值、最长、最短、多少种方法这些通常都是动态规划的强项。而求是否存在的问题有时候用贪心或数学方法更简单。5.2 状态定义想不出来怎么办状态定义是动态规划中最难的一步。想不出来的时候我通常用两个技巧。第一个技巧是从递归函数的参数入手。递归函数的参数通常就是状态定义的维度。比如递归函数是f(i, j)那状态就是dp[i][j]。递归函数的返回值就是dp[i][j]的值。第二个技巧是从问题的最后一步入手。问自己最后一步做了什么操作这个操作依赖哪些子问题比如爬楼梯的最后一步是爬 1 阶或 2 阶所以依赖dp[n-1]和dp[n-2]。零钱兑换的最后一步是选了一枚硬币所以依赖dp[amount-coin]。如果实在想不出来先写暴力递归然后观察递归函数的参数和返回值状态定义自然就出来了。这是最稳妥的方法。5.3 遍历顺序搞错了会怎样遍历顺序错误是动态规划中很隐蔽的 bug。比如dp[i][j]依赖dp[i-1][j]和dp[i][j-1]那遍历顺序必须是外层 i 从小到大内层 j 从小到大。如果内层 j 从大到小那dp[i][j-1]还没计算结果就错了。判断遍历顺序的方法画出状态依赖图确保计算某个状态时它依赖的所有状态都已经计算完毕。对于一维动态规划如果dp[i]依赖dp[i-1]那就从小到大如果依赖dp[i1]那就从大到小。对于二维动态规划通常是从左上到右下但有些问题如背包问题的空间优化版本需要从右下到左上。5.4 空间优化什么时候可以做空间优化是动态规划的进阶技巧。当dp[i]只依赖dp[i-1]和dp[i-2]时可以用滚动变量把空间从 O(n) 降到 O(1)。当dp[i][j]只依赖上一行时可以用一维数组代替二维数组。但空间优化不是必须的。面试中如果时间紧张先写出未优化的版本确保正确性再考虑优化。我见过候选人为了空间优化把代码写得很复杂结果逻辑出错得不偿失。空间优化的前提是不影响可读性。如果优化后代码变得难以理解那不如不优化。面试官更看重的是思路清晰和代码正确而不是极致的空间复杂度。5.5 常见问题速查表问题现象可能原因排查方法结果比预期大很多初始值设置错误检查 dp 数组的初始值是否合理结果比预期小很多状态转移漏了情况检查转移方程是否覆盖所有情况数组越界边界条件没处理检查循环的起止范围结果不稳定遍历顺序错误画出依赖图检查遍历方向超时没有消除重复计算检查是否加了记忆化或动态规划栈溢出递归深度太大改成自底向上或迭代6. 进阶技巧与实战心得6.1 背包问题的统一框架背包问题是动态规划的经典模型包括 01 背包、完全背包、多重背包等变体。掌握背包问题的统一框架能解决一大类问题。01 背包的状态定义dp[i][j]表示前 i 个物品容量为 j 的背包能装的最大价值。状态转移方程dp[i][j] max(dp[i-1][j], dp[i-1][j-weight[i]] value[i])。空间优化后内层循环从大到小遍历。完全背包的状态定义相同但内层循环从小到大遍历。这个区别的原因是01 背包每个物品只能用一次所以计算dp[j]时必须保证dp[j-weight[i]]是上一轮的状态完全背包每个物品可以用无限次所以dp[j-weight[i]]可以是本轮的状态。# 01 背包 for i in range(n): for j in range(capacity, weight[i] - 1, -1): dp[j] max(dp[j], dp[j-weight[i]] value[i]) # 完全背包 for i in range(n): for j in range(weight[i], capacity 1): dp[j] max(dp[j], dp[j-weight[i]] value[i])这个框架可以解决很多变体问题比如零钱兑换就是完全背包的变体分割等和子集就是 01 背包的变体。6.2 区间动态规划的套路区间动态规划的状态定义通常是dp[i][j]表示区间 [i, j] 上的最优解。遍历顺序通常是按区间长度从小到大因为长区间的解依赖短区间的解。经典题目包括最长回文子序列、戳气球、矩阵链乘法。以最长回文子序列为例状态定义dp[i][j]表示字符串 s 在区间 [i, j] 上的最长回文子序列长度。转移方程如果s[i] s[j]那dp[i][j] dp[i1][j-1] 2否则dp[i][j] max(dp[i1][j], dp[i][j-1])。def longestPalindromeSubseq(s): n len(s) dp [[0] * n for _ in range(n)] for i in range(n): dp[i][i] 1 for length in range(2, n 1): for i in range(n - length 1): j i length - 1 if s[i] s[j]: dp[i][j] dp[i1][j-1] 2 else: dp[i][j] max(dp[i1][j], dp[i][j-1]) return dp[0][n-1]区间动态规划的难点在于遍历顺序。必须按区间长度从小到大遍历因为dp[i][j]依赖dp[i1][j-1]、dp[i1][j]、dp[i][j-1]这些区间的长度都比[i, j]小。6.3 状态压缩的技巧状态压缩是用二进制位来表示状态的技巧适用于状态空间是集合的问题。经典题目是旅行商问题和集合覆盖问题。以旅行商问题为例状态定义dp[mask][i]表示已经访问的城市集合为 mask当前在城市 i 的最短路径。mask 是一个二进制数第 k 位为 1 表示城市 k 已访问。状态转移方程dp[mask][i] min(dp[mask ^ (1i)][j] dist[j][i])其中 j 是 mask 中除了 i 之外的城市。def tsp(dist): n len(dist) dp [[float(inf)] * n for _ in range(1 n)] dp[1][0] 0 for mask in range(1 n): for i in range(n): if dp[mask][i] float(inf): 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]) return min(dp[(1 n) - 1][i] dist[i][0] for i in range(n))状态压缩的时间复杂度通常是 O(2^n * n^2)适用于 n 不超过 20 的情况。n 再大就会超时。6.4 我踩过的那些坑第一个坑是忘记处理空输入。有一次面试题目是最长递增子序列我写完代码后面试官问如果数组为空呢我才发现代码会返回错误结果。后来养成了习惯写完动态规划先检查空输入和单元素输入。第二个坑是初始值设得太大导致溢出。用float(inf)做初始值的时候如果做加法运算inf 1还是inf不会溢出。但如果用sys.maxsize做初始值加法就会溢出变成负数。我建议统一用float(inf)省心。第三个坑是二维数组的创建方式。dp [[0] * n] * m这种写法是错误的因为它创建的是 m 个指向同一个列表的引用。修改dp[0][0]会同时修改dp[1][0]。正确的写法是dp [[0] * n for _ in range(m)]。这个坑我踩过不止一次。第四个坑是递归中的可变默认参数。def fib(n, memo{})这种写法memo 会在多次调用之间共享。如果函数被多次调用memo 会保留上一次的结果导致错误。正确的写法是def fib(n, memoNone)然后在函数内部判断if memo is None: memo {}。这些坑看起来很小但在面试中一旦踩中可能就是通过和不通过的区别。建议平时刷题的时候就养成好习惯不要等到面试才注意。6.5 面试中的沟通技巧动态规划题在面试中沟通比代码更重要。我建议按以下顺序和面试官沟通先说出暴力递归的思路包括状态定义和转移方程。这一步展示的是你的思维能力。然后指出递归中的重复计算问题提出用记忆化或动态规划优化。这一步展示的是你的优化意识。接着写出自底向上的代码边写边解释每一行的含义。最后分析时间和空间复杂度并提出可能的优化方向。如果卡住了不要沉默。可以这样说我目前想到的状态定义是 XXX但转移方程还不太确定能不能给我一点提示面试官通常愿意给提示关键是你要展示出思考的过程而不是直接放弃。另外写完代码后一定要手动跑一个简单的测试用例。比如爬楼梯问题跑 n3 的情况验证输出是不是 3。这一步能发现很多低级错误也能让面试官看到你的严谨。7. 刷题路线与练习建议7.1 分阶段刷题路线动态规划的刷题应该分阶段进行不要一上来就刷难题。第一阶段是入门题包括爬楼梯、斐波那契数列、零钱兑换。这些题的状态定义和转移方程都很直观适合建立信心。第二阶段是经典模型题包括 01 背包、完全背包、最长递增子序列、最长公共子序列。这些题覆盖了动态规划的主要模型刷完之后能识别大部分题目的类型。第三阶段是变体题和综合题包括编辑距离、戳气球、正则表达式匹配。这些题的状态定义需要一些技巧适合提升能力。第四阶段是状态压缩和区间动态规划包括旅行商问题、最长回文子序列。这些题难度较高适合冲刺高级岗位。每个阶段建议刷 10 到 15 道题不要贪多。刷题的质量比数量重要。每道题都要做到能写出递归解、能写出记忆化解、能写出自底向上解、能分析复杂度、能处理边界情况。7.2 如何高效复习动态规划的题目容易忘复习很重要。我建议用三遍法复习。第一遍是刷题时写出完整解法并记录思路。第二遍是三天后不看答案重新写一遍检查是否还记得。第三遍是一周后只看题目口述思路和转移方程不写代码。另外建议建一个错题本记录自己做错的题和踩过的坑。每次复习的时候先看错题本再看新题。错题本上的题要反复做直到能流畅写出为止。动态规划的进步不是线性的。有时候刷了十几道题感觉还是不会但突然某一天就开窍了。关键是坚持不要因为一时卡壳就放弃。7.3 面试前的冲刺建议面试前一周不要再刷新题而是复习经典题。把爬楼梯、零钱兑换、最长递增子序列、编辑距离、01 背包这几道题写熟做到不看答案能默写。面试前一天早点休息不要熬夜刷题。动态规划需要清晰的思维疲劳状态下容易出错。面试中如果遇到没见过的题先深呼吸然后按四步框架分析定义状态、写转移方程、确定初始条件、确定遍历顺序。即使最后没写出完整代码只要思路清晰面试官也会给分。最后分享一个我个人的习惯每次写完动态规划代码我都会用一个小例子手动模拟一遍表格的填充过程。这个习惯帮我发现了无数个边界错误和遍历顺序错误。看起来费时间但实际上比调试省时间得多。