递归和动态规划这两个词几乎是每个刷算法题的人绕不开的两座大山。我见过太多人递归能看懂但自己写就绕晕动态规划的状态转移方程更是看一眼就头疼。更别提面试的时候面试官一句“你这递归能优化吗”直接把人问出一身冷汗。这篇文章就是写给那些被递归和动态规划反复折磨、想在面试中真正把这类题拿下的朋友。我会从两者的本质联系讲起把递归怎么一步步演化成动态规划的全过程拆开揉碎再配合几道经典面试题的完整推导让你不仅知道怎么写更知道为什么这么写。读完你至少能做到看到一道题能判断该用递归还是动态规划能自己推导状态转移方程能说清楚记忆化搜索和递推的区别与取舍。1. 递归和动态规划到底是什么关系1.1 递归的本质把大问题拆成同类小问题递归的核心思想就一句话一个问题的解可以通过它更小规模的同类问题的解来得到。你不需要一开始就想清楚每一步怎么走只需要定义好“当前这一步做什么”和“什么时候停下来”剩下的交给函数自己调用自己。打个生活化的比方。你排队买奶茶想知道自己排在第几位。你懒得从头数就问前面那个人“你排第几”前面的人再问他前面的人一直问到第一个人说“我排第一”然后答案一层层传回来你前面的人告诉你他是第几你加一就是自己的位置。这就是递归递是往前问的过程归是答案传回来的过程。用代码表达就是def position(n): if n 1: # 终止条件第一个人 return 1 return position(n - 1) 1 # 当前 前面的人的位置 1这里有两个关键点。第一终止条件必须有否则函数会无限调用下去直到栈溢出。第二当前层和下一层的关系必须明确也就是position(n)和position(n-1)之间的数学关系。这两点缺一不可。递归的代码往往非常简洁优雅因为它直接对应了问题的数学定义。比如斐波那契数列的定义是f(n) f(n-1) f(n-2)递归写出来几乎和定义一模一样。但优雅的代价是性能——这一点后面会详细展开。1.2 动态规划的本质用表格记住算过的答案动态规划的核心思想是把原问题拆成若干子问题先求解子问题再把子问题的解存起来避免重复计算最终组合出原问题的解。还是用斐波那契举例。递归求f(5)的时候f(3)会被算好几次f(2)被算更多次。n 稍微大一点计算量就爆炸式增长。动态规划的做法是我从f(1)和f(2)开始一路往上算到f(5)每一步的结果都存下来后面要用直接取不重新算。def fib(n): if n 2: return 1 dp [0] * (n 1) dp[1] dp[2] 1 for i in range(3, n 1): dp[i] dp[i - 1] dp[i - 2] return dp[n]你看同样是求斐波那契递归是“从目标往下问”动态规划是“从底往上推”。方向不同但解决的问题是同一个。1.3 两者的桥梁重叠子问题和最优子结构递归和动态规划能扯上关系靠的是两个概念重叠子问题和最优子结构。重叠子问题说的是递归展开的过程中同一个子问题被反复计算。斐波那契是最典型的例子f(3)在算f(5)的过程中被调用了两次f(2)被调用了三次。如果一个问题拆开后子问题之间完全独立、不重复那用普通递归或者叫分治就够了比如归并排序犯不着上动态规划。最优子结构说的是原问题的最优解可以由子问题的最优解推导出来。这句话听起来抽象其实就是在说你能写出一个正确的递推关系。比如“爬到第 n 阶楼梯的方法数 爬到第 n-1 阶的方法数 爬到第 n-2 阶的方法数”这就是一个最优子结构的体现。所以两者的关系可以这样总结递归是自顶向下的解题思路动态规划是自底向上的解题思路它们描述的是同一个递推关系。当递归存在大量重复计算时加上记忆化把算过的存起来就变成了记忆化搜索再把记忆化搜索改成自底向上的迭代就是标准的动态规划。这条演化路径是我理解这类问题的核心线索后面每一道题我都会沿着这条线来拆。2. 从递归到动态规划的完整演化路径2.1 第一步写出暴力递归拿到一道题第一步永远是先写出暴力递归。不要一上来就想动态规划那样容易卡在状态定义上。暴力递归的好处是它直接对应问题的定义不容易写错而且它是后续优化的基础。以经典的“爬楼梯”为例。题目是每次可以爬 1 阶或 2 阶爬到第 n 阶有多少种方法。暴力递归的思路要爬到第 n 阶最后一步要么是从第 n-1 阶爬 1 阶上来的要么是从第 n-2 阶爬 2 阶上来的。所以爬到第 n 阶的方法数 爬到第 n-1 阶的方法数 爬到第 n-2 阶的方法数。def climb(n): if n 1: return 1 if n 2: return 2 return climb(n - 1) climb(n - 2)这段代码的时间复杂度是 O(2^n)因为每次调用都分裂成两个分支。n40 的时候就已经慢得离谱了。但先别管性能这一步的目的是把递推关系写对。2.2 第二步加记忆化消除重复计算暴力递归慢在哪慢在同一个climb(k)被反复计算。那解决办法很直接算过一次就存起来下次直接取。def climb(n, memoNone): if memo is None: memo {} if n 1: return 1 if n 2: return 2 if n in memo: return memo[n] memo[n] climb(n - 1, memo) climb(n - 2, memo) return memo[n]这就是记忆化搜索。它的本质还是递归只是加了一个缓存。时间复杂度从 O(2^n) 直接降到 O(n)因为每个子问题只算一次。空间复杂度是 O(n)缓存和递归栈各占一份。记忆化搜索有个好处它保留了递归的思考方式写起来自然而且不需要考虑计算顺序。你不需要想“我该从哪个状态开始推”只需要在递归的基础上加几行缓存代码。对于刚接触动态规划的人来说这是最好的过渡方式。2.3 第三步改成自底向上的递推记忆化搜索虽然快但递归调用有栈开销而且当 n 很大的时候可能栈溢出。这时候把它改成自底向上的迭代就是标准的动态规划了。自底向上的思路是既然我知道dp[1]1、dp[2]2那我直接从 3 开始往上算每一步都依赖前两步的结果。def climb(n): if n 1: return 1 if n 2: return 2 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)。代码里没有递归全是循环稳定可靠。2.4 第四步空间优化能省则省很多时候我们不需要存整个 dp 数组只需要存最近几个状态。爬楼梯这道题dp[i]只依赖dp[i-1]和dp[i-2]所以用两个变量滚动更新就够了。def climb(n): if n 1: return 1 if n 2: return 2 prev2, prev1 1, 2 for i in range(3, n 1): cur prev1 prev2 prev2 prev1 prev1 cur return prev1空间复杂度从 O(n) 降到 O(1)。这就是动态规划的终极形态。把这条路径总结成一张表阶段写法时间复杂度空间复杂度特点暴力递归直接递归O(2^n)O(n) 栈思路直观性能差记忆化搜索递归缓存O(n)O(n)保留递归思路消除重复自底向上迭代填表O(n)O(n)无栈开销顺序清晰空间优化滚动变量O(n)O(1)极致省空间注意不是所有题都能做空间优化。只有当dp[i]只依赖有限个前面的状态时才能滚动。如果依赖的状态跨度很大还是老老实实用数组。3. 动态规划解题的核心框架3.1 状态定义动态规划最关键的一步动态规划最难的地方不是写代码而是定义状态。状态定义对了转移方程往往水到渠成状态定义错了怎么推都推不出来。什么叫状态状态就是“我要用一个什么样的变量组合来描述当前面临的子问题”。比如爬楼梯状态就是“爬到第 i 阶的方法数”用dp[i]表示。比如背包问题状态是“前 i 个物品、容量为 j 时的最大价值”用dp[i][j]表示。状态定义有一个实用的检验方法你定义的状态能不能唯一确定一个子问题如果能那这个状态就是合格的。比如dp[i]表示爬到第 i 阶的方法数给定 i 就能唯一确定答案合格。如果你定义dp[i]表示“爬了 i 步”那就乱了因为爬到同一阶可能用了不同的步数状态不唯一。我个人的经验是状态定义通常和题目问的东西直接相关。题目问“有多少种方法”状态就是“方法数”题目问“最大价值”状态就是“最大价值”题目问“最少需要几步”状态就是“最少步数”。先把题目问的东西作为状态的核心再考虑需要几个维度来描述子问题。3.2 转移方程从最后一步倒推状态定义好之后下一步是推导转移方程。我的习惯是从最后一步倒推考虑到达最终状态的前一步可能是什么然后把所有可能的情况列出来。还是爬楼梯。最终状态是dp[n]到达第 n 阶的最后一步要么从 n-1 阶爬 1 阶要么从 n-2 阶爬 2 阶。所以dp[n] dp[n-1] dp[n-2]。就这么简单。再看一个稍微复杂点的打家劫舍。一排房子每间有不同金额不能偷相邻的两间求最大金额。状态定义dp[i]表示考虑前 i 间房子能偷到的最大金额。最后一步倒推对于第 i 间房子只有两种选择——偷或者不偷。如果偷第 i 间那第 i-1 间不能偷最大金额是dp[i-2] nums[i]如果不偷第 i 间最大金额就是dp[i-1]。所以转移方程是dp[i] max(dp[i-1], dp[i-2] nums[i])你看从最后一步倒推把所有可能性列全转移方程自然就出来了。这个方法我用了很多年几乎没失手过。3.3 边界条件别让数组越界边界条件是动态规划里最容易出错的地方。所谓边界就是最小子问题的解也就是递推的起点。爬楼梯的边界是dp[1]1、dp[2]2。打家劫舍的边界是dp[0]0、dp[1]nums[0]。这些值必须手动初始化否则循环跑起来要么越界要么结果错误。我踩过的一个坑是有时候边界不止一个而且容易漏。比如有的题dp[0]和dp[1]都要初始化我只初始化了dp[0]结果dp[2]算出来是错的。后来我养成了一个习惯写完转移方程后先手动把 i0、i1、i2 代进去算一遍看看边界够不够。如果 i2 的时候用到了dp[0]和dp[1]那这两个都得初始化。3.4 遍历顺序确保依赖的状态已经算好遍历顺序的原则只有一条当你计算dp[i]的时候它依赖的所有状态必须已经计算完毕。对于一维 dp如果dp[i]依赖dp[i-1]和dp[i-2]那从前往后遍历就行。对于二维 dp比如背包问题dp[i][j]依赖dp[i-1][j]和dp[i-1][j-w]那外层循环遍历物品 i内层循环遍历容量 j顺序不能反。有一类题比较特殊比如完全背包内层循环需要从前往后遍历而 0-1 背包内层循环需要从后往前遍历。这个区别的原因在于完全背包允许重复选同一物品从前往后遍历时dp[j-w]已经是本层更新过的值相当于可以多次选0-1 背包不允许重复选从后往前遍历时dp[j-w]还是上一层的值保证每个物品只选一次。这个点面试经常考值得单独记一下。4. 经典面试题实战拆解4.1 最长递增子序列一维 dp 的典型代表题目给一个无序整数数组求最长递增子序列的长度。子序列不要求连续。这道题的状态定义稍微需要想一下。dp[i]定义为以 nums[i] 结尾的最长递增子序列长度。注意“以 nums[i] 结尾”这个限定非常重要它保证了状态的可转移性。转移方程对于每个 i遍历它前面所有的 jj i如果nums[j] nums[i]说明 nums[i] 可以接在 nums[j] 后面此时dp[i] max(dp[i], dp[j] 1)。def lengthOfLIS(nums): if not nums: return 0 n len(nums) dp [1] * n for i in range(1, 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)。这道题的边界是dp[i]初始化为 1因为每个元素本身至少构成一个长度为 1 的递增子序列。实操心得这道题有一个 O(n log n) 的优化解法用二分查找维护一个“ tails 数组”。但面试的时候先把 O(n^2) 的 dp 写对写清楚再提优化比一上来就写最优解但讲不清楚要稳得多。4.2 零钱兑换完全背包的经典应用题目给若干种硬币面额和一个目标金额求凑出目标金额所需的最少硬币数每种硬币可以用无限次。状态定义dp[i]表示凑出金额 i 所需的最少硬币数。转移方程对于金额 i遍历每种硬币 coin如果i coin那dp[i] min(dp[i], dp[i-coin] 1)。def coinChange(coins, amount): dp [float(inf)] * (amount 1) dp[0] 0 for i in range(1, amount 1): for coin in coins: if i coin: dp[i] min(dp[i], dp[i - coin] 1) return dp[amount] if dp[amount] ! float(inf) else -1边界是dp[0] 0凑出金额 0 需要 0 枚硬币。其他初始化为无穷大表示暂时凑不出来。这道题的遍历顺序值得说一下。外层遍历金额内层遍历硬币这是完全背包的标准写法。因为每种硬币可以用无限次所以内层从前往后遍历dp[i-coin]用的是本层已经更新过的值。4.3 编辑距离二维 dp 的硬骨头题目给两个字符串求把第一个字符串变成第二个字符串所需的最少操作次数。操作有三种插入一个字符、删除一个字符、替换一个字符。状态定义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] 1def 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把前 i 个字符变成空串需要删除 i 次和dp[0][j] j把空串变成前 j 个字符需要插入 j 次。这道题是二维 dp 的典型代表面试出现频率极高。它的难点在于状态定义和转移方程的推导但只要按照“从最后一步倒推”的方法把三种操作列全方程就能写出来。4.4 三道题的横向对比题目状态维度转移方程核心遍历顺序易错点最长递增子序列一维遍历前面所有 j从前往后状态要限定“以 i 结尾”零钱兑换一维遍历每种硬币从前往后初始化无穷大dp[0]0编辑距离二维分相等/不等讨论双层从前往后边界初始化容易漏5. 常见问题与排查技巧实录5.1 递归栈溢出怎么办递归深度太大的时候Python 默认递归深度是 1000超过就报RecursionError。解决办法有两个一是改成迭代也就是自底向上的动态规划二是手动设置递归深度上限。但第二种只是权宜之计真正靠谱的还是改成迭代。我在实际刷题的时候只要发现递归深度可能超过几百就直接上动态规划不给自己找麻烦。5.2 状态转移方程推不出来怎么办推不出来通常是因为状态定义得不好。我的排查步骤是先问自己题目问的是什么把问的东西作为状态的核心。再问这个状态能不能唯一确定一个子问题如果不能加维度。然后从最后一步倒推把所有可能的前一步列出来。如果还是推不出来试着把暴力递归写出来然后观察递归函数的参数——参数往往就是状态。这个方法我用了很多次基本上没有推不出来的题。5.3 初始化踩过的坑最常见的坑是dp[0]的语义。有的题dp[0]表示“前 0 个元素”有的题表示“第 0 个元素”语义不同初始化值也不同。我踩过最惨的一次是把dp[0]初始化成 0但实际上应该是 1导致后面全错排查了半小时才发现。避坑技巧写完初始化后手动把 i0、i1 代进去跑一遍看看结果是否符合预期。这一步花不了一分钟但能省下大量调试时间。5.4 遍历顺序搞反了前面提过0-1 背包和完全背包的内层遍历顺序是相反的。搞反了不会报错但结果会错而且很难发现。我的记忆方法是0-1 背包每个物品只能用一次所以从后往前保证用的是上一层的值完全背包每个物品能用无限次所以从前往后用的是本层更新过的值。5.5 常见问题速查表问题现象可能原因排查方法结果偏大重复计算了某些状态检查遍历顺序确认依赖状态是否已算好结果偏小漏掉了某些转移情况重新从最后一步倒推列全所有可能数组越界边界条件没处理好检查 dp 数组大小和索引范围递归超时没有记忆化加缓存或改成自底向上结果不稳定初始化值不对手动代入小规模数据验证6. 面试中的表达技巧与心态6.1 先说思路再写代码面试的时候最忌讳的是上来就闷头写代码。正确的做法是先用一两句话把状态定义和转移方程说清楚让面试官知道你想明白了然后再动手写。比如“我定义 dp[i] 为爬到第 i 阶的方法数转移方程是 dp[i] dp[i-1] dp[i-2]边界是 dp[1]1、dp[2]2”说完这几句面试官心里就有底了。6.2 主动提优化写完暴力递归后主动说“这里存在重复计算我可以加记忆化把复杂度从 O(2^n) 降到 O(n)”然后写出来。再主动说“记忆化搜索可以改成自底向上的迭代省掉递归栈开销”再写出来。最后说“由于只依赖前两个状态空间可以优化到 O(1)”。这一套下来面试官会觉得你对动态规划的理解非常系统。6.3 卡住了怎么办卡住的时候不要沉默把你在想的东西说出来。比如“我在想状态应该定义成一维还是二维”“我在考虑最后一步是从哪里来的”。面试官往往会在你表达思路的过程中给你提示比你一个人闷想要好得多。我个人的体会是递归和动态规划这类题考察的不是你背了多少道题而是你有没有一套系统的分析方法。状态定义、转移方程、边界条件、遍历顺序这四步走下来大部分题都能拿下。剩下的就是多练练到看到题目就能条件反射地想到状态怎么定义。这个内容后续还可以这样扩展把区间 dp、树形 dp、状态压缩 dp 这些变种也按同样的框架拆一遍基本上动态规划这一块就通了。