1. 从一次面试翻车说起为什么递归写得好好的面试官却让我重写几年前我帮朋友做模拟面试出了一道很经典的题爬楼梯一次可以走1阶或2阶问走到第n阶有多少种走法。朋友三秒钟写出递归版本代码简洁得像首诗然后自信地看着我。我问了一句n等于50的时候你这台笔记本跑得动吗他愣了一下跑了一下风扇直接起飞等了十几秒还没出结果。那一刻他才意识到递归和动态规划之间隔着的不是语法而是对计算过程的根本理解。这个场景在算法面试里太常见了。很多人学递归的时候觉得函数自己调用自己很优雅学动态规划的时候又觉得状态转移方程很玄学两者像是两个独立的知识点。但实际上动态规划本质上就是递归加上一层记忆把递归过程中重复计算的部分缓存下来用空间换时间。你如果能把递归的调用树画清楚动态规划的状态定义和转移方程几乎是自然浮现的。这篇内容适合三类人一是刚接触递归、能写但说不清执行流程的初学者二是刷题时能看懂题解但自己想不到状态转移的面试准备者三是想系统梳理这两块知识、把零散经验串成体系的中级开发者。我会从递归的执行模型讲起拆解它为什么会慢、慢在哪里然后一步步引出记忆化搜索和自底向上的动态规划最后用几道高频面试题把两种思路对照着写一遍。全程不堆术语每个结论都配执行过程或代码验证你可以直接拿着对照自己的代码改。2. 递归不是函数调用自己这么简单调用栈与执行顺序的真相2.1 递归的执行模型栈帧的压入与弹出很多人对递归的理解停留在函数自己调自己这个描述没错但没用。真正要理解的是调用栈这个结构。每次函数调用系统会在栈上开辟一块空间叫栈帧里面存着当前函数的参数、局部变量和返回地址。递归调用时新的栈帧压在旧的上面只有最顶层的栈帧执行完弹出后下面那层才能继续。拿最简单的阶乘举例def factorial(n): if n 1: return 1 return n * factorial(n - 1)调用factorial(4)时栈的变化是这样的先压入factorial(4)它需要factorial(3)的结果于是压入factorial(3)依次压到factorial(1)。此时栈顶factorial(1)直接返回1并弹出factorial(2)拿到1算出2返回并弹出一路回退到factorial(4)得到24。这个先压到底、再弹回来的过程就是递归的本质。理解这一点非常关键因为它直接决定了两件事第一递归深度受栈空间限制Python默认递归深度大约1000层超过就报RecursionError第二递归的返回值是在回退阶段计算的所以如果你在递归调用之前做操作那是去程在调用之后做操作那是回程两者顺序完全相反。2.2 为什么递归代码短却容易慢重复子问题的代价回到爬楼梯问题。递归写法是这样的def climb(n): if n 2: return n return climb(n - 1) climb(n - 2)代码只有三行但计算climb(5)时调用树是这样的climb(5)要算climb(4)和climb(3)climb(4)又要算climb(3)和climb(2)。注意climb(3)被计算了两次。继续往下climb(2)会被计算更多次。n越大重复计算的规模呈指数级膨胀。我实测过climb(35)在我的机器上大约要跑3秒climb(40)要30秒以上climb(50)基本就是分钟级别了。而这个问题本身的状态空间只有n个也就是说理论上只需要算n次实际却算了2的n次方次。这就是递归低效的根源它忠实地执行了你写的逻辑但你的逻辑里包含了大量重复劳动。提示判断一个递归问题是否有病就看它的调用树里有没有重复出现的节点。有重复就有优化空间没有重复比如归并排序的递归那它本身就是高效的。2.3 递归树把抽象调用变成看得见的结构要优化递归第一步是把调用树画出来。以爬楼梯climb(5)为例根节点是5左子节点是4右子节点是34下面又分3和23下面分2和1。画完之后你会发现标着3的节点出现了两次标着2的节点出现了三次。这棵树给了我们两个信息一是哪些子问题被重复计算了二是子问题之间的依赖关系。动态规划要做的就是把这棵树里重复的节点合并让每个子问题只算一次。具体怎么合并就是接下来要讲的记忆化和自底向上两种路径。画递归树这个动作我建议你在草稿纸上手动做不要只在脑子里想。手画的过程会强迫你展开每一层很多你自以为想清楚的地方一画就露馅。我见过太多人说自己理解递归结果画到第三层就卡住了。3. 记忆化搜索给递归加一本备忘录不改逻辑只加缓存3.1 记忆化的核心操作查表与存表记忆化搜索的思路极其朴素既然重复计算是浪费那我算过一次就记下来下次直接查。具体到代码就是加一个字典或数组当缓存进入函数先查算完再存。def climb_memo(n, memoNone): if memo is None: memo {} if n 2: return n if n in memo: return memo[n] memo[n] climb_memo(n - 1, memo) climb_memo(n - 2, memo) return memo[n]改动只有三行初始化memo、查memo、存memo。但效果是质变。同样算climb(50)记忆化版本几乎是瞬间返回因为每个n只被真正计算一次其余都是O(1)的查表。这里有个细节值得说memo的key选择。对于单参数递归n本身就是key对于多参数递归比如二维网格路径问题key就得是(i, j)这样的元组。key选错会导致缓存命中不了等于白加。我见过有人用字符串拼接当key能跑但慢因为字符串哈希和比较的开销比元组大。3.2 记忆化 vs 纯递归复杂度是怎么降下来的纯递归爬楼梯的时间复杂度是O(2^n)因为调用树是指数级展开的。加了记忆化之后每个不同的n只会触发一次真正的计算其余都是查表所以时间复杂度降到O(n)空间复杂度也是O(n)因为memo要存n个结果递归栈深度也是n。这个降维打击的幅度用数字感受一下n50时2^50大约是10的15次方而n本身只有50。从千万亿次计算降到50次计算这就是记忆化的威力。但记忆化不是没有代价。它保留了递归的调用栈所以空间上比自底向上多了一层栈开销。而且递归深度受系统限制n特别大的时候还是会栈溢出。所以记忆化适合逻辑上就是递归、状态转移不明显的问题写起来快改起来也快。3.3 什么时候记忆化就够了什么时候必须转自底向上我的经验是面试时如果时间紧先写记忆化能过就行。因为记忆化保留了递归的直观结构你不需要重新组织计算顺序只要加缓存。很多面试官也接受记忆化作为动态规划的一种形式。但有两种情况必须转自底向上。第一种是递归深度可能超限比如n达到10的5次方递归栈扛不住。第二种是需要做空间优化比如滚动数组这个在记忆化里很难做因为递归的访问顺序是跳跃的而自底向上是顺序的可以只保留最近几行状态。判断标准很简单如果状态转移只依赖前一个或前几个状态那自底向上加滚动数组能把空间从O(n)降到O(1)这时候就值得转。如果依赖关系复杂记忆化反而更清晰。4. 自底向上动态规划把递归的回程改成去程4.1 状态定义动态规划最难的一步动态规划的核心是状态定义和状态转移方程。状态定义就是回答dp[i]代表什么。这句话听起来简单但它是整个动态规划里最容易翻车的地方。以爬楼梯为例dp[i]定义为走到第i阶的走法数。这个定义一旦确定转移方程就自然出来了走到第i阶要么从第i-1阶走1步上来要么从第i-2阶走2步上来所以dp[i] dp[i-1] dp[i-2]。边界条件是dp[1] 1dp[2] 2。对比一下递归版本你会发现转移方程其实就是递归函数体里那行return只是把函数调用换成了数组下标。这就是为什么我说动态规划是递归的另一种写法递归是我要算n得先算n-1和n-2自底向上是我先算1和2再算3一路算到n。方向反了结果一样。def climb_dp(n): if n 2: return n dp [0] * (n 1) dp[1], dp[2] 1, 2 for i in range(3, n 1): dp[i] dp[i - 1] dp[i - 2] return dp[n]4.2 从递归树到填表计算顺序为什么可以反过来递归的计算顺序是从根到叶再从叶回根自底向上是从叶到根一路向上。为什么可以反过来因为子问题的解不依赖于父问题。dp[3]只依赖dp[1]和dp[2]不依赖dp[4]。这种依赖关系是单向的所以我们可以从最小的子问题开始逐个填表保证算到某个状态时它依赖的状态都已经算好了。这个保证依赖先算的顺序就是拓扑序。对于一维dp拓扑序就是下标从小到大对于二维dp可能是按行填、按列填或者按对角线填。填表顺序错了用到的是还没算的默认值结果就全错。我见过有人写二维dp时行列搞反跑出来全是0debug半天。4.3 空间优化滚动数组把O(n)压到O(1)爬楼梯的dp数组其实只需要保留最近两个值因为dp[i]只依赖dp[i-1]和dp[i-2]。所以可以用两个变量滚动更新def climb_opt(n): if n 2: return n a, b 1, 2 for i in range(3, n 1): a, b b, a b return b空间从O(n)降到O(1)。这个技巧在面试里是加分项因为它说明你不仅会写还理解状态之间的依赖范围。判断能不能滚动就看转移方程用到了前面几个状态。用到前两个两个变量够用到前k个就得k个变量或一个长度为k的数组。但要注意滚动数组会丢失中间状态如果题目要求返回完整路径而不只是最优值那就不能滚动。这是取舍不是无脑优化。5. 三道高频面试题的递归与DP对照实战5.1 打家劫舍从选或不选到状态转移题目是一排房子每家有金额不能偷相邻两家求最大金额。递归思路是对于第i家要么偷那第i-1家不能偷结果为nums[i] rob(i-2)要么不偷结果为rob(i-1)。取两者最大值。def rob_memo(nums): memo {} def dfs(i): if i 0: return 0 if i in memo: return memo[i] memo[i] max(dfs(i - 1), nums[i] dfs(i - 2)) return memo[i] return dfs(len(nums) - 1)转成自底向上dp[i]定义为前i家能偷到的最大金额转移方程dp[i] max(dp[i-1], nums[i] dp[i-2])。这里的状态定义和递归的dfs(i)含义一致只是方向反了。def rob_dp(nums): if not nums: return 0 n len(nums) if n 1: return nums[0] dp [0] * n dp[0] nums[0] dp[1] max(nums[0], nums[1]) for i in range(2, n): dp[i] max(dp[i - 1], nums[i] dp[i - 2]) return dp[-1]这道题的关键洞察是**选或不选这个决策模型**。很多动态规划问题都可以套这个框架每个位置做一个二元决策取最优。识别出这个模式转移方程就很好写。5.2 零钱兑换当递归遇到无解和多分支题目是给若干硬币面额和一个目标金额求凑出目标的最少硬币数凑不出返回-1。递归思路是对于金额amount尝试每一种硬币如果用了这枚硬币剩下amount - coin结果加1。def coin_memo(coins, amount): memo {} def dfs(rem): if rem 0: return 0 if rem 0: return float(inf) if rem in memo: return memo[rem] best float(inf) for c in coins: best min(best, dfs(rem - c) 1) memo[rem] best return best res dfs(amount) return res if res ! float(inf) else -1这道题比爬楼梯复杂的地方在于分支数不固定取决于硬币种类数。而且有无解的情况用float(inf)表示不可达。转成自底向上dp[i]是凑出金额i的最少硬币数初始化dp[0]0其余为inf然后对每个金额遍历硬币。def coin_dp(coins, amount): dp [float(inf)] * (amount 1) dp[0] 0 for i in range(1, amount 1): for c in coins: if i c: dp[i] min(dp[i], dp[i - c] 1) return dp[amount] if dp[amount] ! float(inf) else -1注意这里两层循环的顺序不能随便换。外层遍历金额、内层遍历硬币得到的是组合数意义上的最优如果外层硬币、内层金额在某些求方案数的问题里会变成排列数。这道题求的是最少数量顺序不影响结果但换成求凑出金额的方案数时顺序就决定了答案对不对。这是动态规划里非常容易踩的坑。5.3 最长递增子序列递归思路为什么不如DP直观题目是求数组中最长严格递增子序列的长度。这道题用纯递归写会很难受因为子序列不是连续的子数组选择哪个元素作为下一个依赖于前一个选了谁。递归需要带上前一个元素的下标作为参数。def lis_memo(nums): n len(nums) memo {} def dfs(prev, cur): if cur n: return 0 key (prev, cur) if key in memo: return memo[key] taken 0 if prev -1 or nums[cur] nums[prev]: taken 1 dfs(cur, cur 1) not_taken dfs(prev, cur 1) memo[key] max(taken, not_taken) return memo[key] return dfs(-1, 0)状态是二维的(prev, cur)复杂度O(n^2)。转成自底向上dp[i]定义为以nums[i]结尾的最长递增子序列长度转移是dp[i] max(dp[j]) 1其中j i且nums[j] nums[i]。def lis_dp(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)这道题很好地说明了状态定义的选择会极大影响解法复杂度。递归版本的状态(prev, cur)是二维的而DP版本把状态压缩成一维的以i结尾因为最优子结构允许我们只关心结尾元素。这种重新定义状态让问题变简单的能力是动态规划进阶的关键。6. 面试现场怎么选递归、记忆化、DP的决策清单6.1 三分钟判断该用哪种写法面试时时间有限不可能每种都写一遍。我的决策流程是这样的场景特征推荐写法理由问题天然是树形结构如遍历、分治纯递归没有重复子问题加缓存反而累赘有重复子问题但状态转移不明显记忆化搜索保留递归直观性改动小递归深度可能超限或需要空间优化自底向上DP避免栈溢出可滚动数组面试官明确要求非递归自底向上DP直接满足要求时间只剩5分钟记忆化搜索最快写出正确解这个表不是死的但能帮你在紧张时快速决策。核心判断依据就一条有没有重复子问题。有就往记忆化或DP走没有纯递归就是最优解。6.2 写DP时的三个自检问题写完动态规划代码别急着说好了先问自己三个问题第一状态定义说清楚了吗能不能用一句话说出dp[i]代表什么。如果说不清说明你自己都没想明白代码大概率有bug。第二边界条件对吗dp[0]、dp[1]这些初始值以及数组长度是n还是n1这些细节错一个就全错。我习惯写完先手动跑一个最小用例比如n1、n2看输出对不对。第三遍历顺序保证依赖先算了吗一维dp通常从小到大没问题但二维dp要检查行列顺序背包问题要检查是正序还是逆序。这个检查能拦住大部分结果莫名其妙的bug。6.3 我踩过的坑状态定义错一步后面全白写说个我自己的翻车经历。有一次做最长公共子序列我定义dp[i][j]为字符串A前i个和字符串B前j个的最长公共子序列长度这个定义是对的。但在写转移时我下意识写成了dp[i][j] dp[i-1][j-1] 1当字符相等时忘了考虑字符不等时应该取max(dp[i-1][j], dp[i][j-1])。结果跑出来答案偏小debug了二十分钟才发现是漏了分支。这个坑的教训是转移方程要覆盖所有情况。字符相等时有一种选择字符不等时有多种选择每种都要写进去。写完转移方程拿一个具体例子手动推一遍比盯着代码看有效得多。另一个常见坑是数组越界。dp[i-1]在i0时会越界所以要么把dp数组开大一位用dp[0]当哨兵要么在循环里从1开始并单独处理i0。两种都行但要统一别一半用哨兵一半不用。7. 把递归树画在纸上一个让我受益至今的习惯我到现在做动态规划题还是会先在纸上画递归树。不是为了给别人看是为了让自己确认两件事子问题是什么以及子问题之间怎么复用。画完之后状态定义和转移方程基本就是照着树抄下来。这个方法看起来笨但它把抽象的状态转移变成了具体的图形。你不需要凭空想出dp[i] dp[i-1] dp[i-2]你只需要看着树把重复的节点圈出来然后决定是从上往下算记忆化还是从下往上算自底向上。递归和动态规划从来不是两个知识点它们是同一个问题的两种视角递归是我要什么动态规划是我有什么。把这两个视角打通面试题就只是换个壳的同一类问题。最后分享一个小技巧如果你在面试里卡住了就跟面试官说我先画一下递归树。这个动作既争取了思考时间又展示了你分析问题的过程比干坐着强得多。而且很多时候画着画着思路就出来了。