1. 先说结论为什么“递推”值得单独写一篇没把递推吃透就去做动态规划大概率和没学会走就想跑一个下场。我见过太多人在刷题时对着“爬楼梯”“斐波那契”发愁第一反应是写个递归跑跑看跑通了还挺高兴结果面试官一问“空间能不能优化到O(1)”“如果n是10的18次方怎么办”当场就卡住了。递推英文叫 Recurrence中文也叫递推式、递归关系、迭代关系。它的本质就一句话用已知项通过固定关系式推出未知项。看着简单但它是后面所有动态规划、状态机、矩阵快速幂、概率DP这些东西的骨架。你可以不理解状态转移方程这个名词但你得先能写出一个递推式。这篇博客没有花架子我把递推从“是什么”一路讲到“怎么优化”“怎么避坑”代码放全边界条件说清踩过的坑末了再聊两句我平时怎么快速识别一道新题能不能用递推。不管你是刚接触算法的代码新人还是刷题半年的进阶选手这篇都值得你花十分钟好好读一遍。2. 递推和递归的区别一句话就能说透很多资料把递推和递归混着写其实这俩的思考方向正好相反。递归是“自顶向下”先假设一个大规模问题能拆成小规模问题再一层层回溯组装结果递推是“自底向上”从小规模结果出发一个个往后推到大规模。举一个最简单的例子斐波那契数列F(n) F(n-1) F(n-2)其中F(1)1, F(2)1。如果写递归def fib_rec(n): if n 2: return 1 return fib_rec(n-1) fib_rec(n-2)这段代码本身没错逻辑也清楚但你试试跑n45慢到怀疑人生。因为它的调用树里有大量重复计算fib(40)在fib(45)的递归树里被算了不知道多少遍——这不叫优雅这叫指数级浪费。如果写递推def fib_iter(n): if n 2: return 1 a, b 1, 1 for _ in range(3, n 1): a, b b, a b return b同样求n45瞬间跑完空间只用了两个变量。这就是递推的威力每个状态只算一次顺着逻辑链往下推绝不回头。提示递推并不是简单地把递归改成循环。递归的难点在“怎么拆”递推的难点在“怎么定起点、怎么列关系式、怎么保证推的时候不依赖未计算的值”。你如果能把一个递归问题改成递推写出来说明你对问题结构的理解已经到位了。3. 递推的完整思考框架我长期用的就四步3.1 第一步定义状态想清楚“我到底要算什么东西”任何递推的第一步都是确定状态也就是想清楚你记录的是什么量。这个量可以是数列的第 n 项可以是走到第 i 级台阶的方案数也可以是二维矩阵里某个格子的最短路径值。状态定义得好不好直接决定后面是顺畅推到底还是越推越乱。我的经验是状态里优先带“位置”或者“长度”这类编号参数比如dp[i]表示处理完前 i 个元素的结果dp[i][j]表示从左上角走到(i,j)的方案数。编号参数让你能天然形成一个推进的顺序后面推关系式时就容易想到“dp[i]能不能由dp[i-1]、dp[i-2]推过来”。很多新手一上来就定义dp[n]表示最终答案中间过程全丢了结果关系式根本列不出来——这就是状态定义太粗糙的问题。宁可状态里多带一维也别少带信息。3.2 第二步找递推关系式把“当前状态”和“之前状态”挂上钩这是整个递推里最核心、也最考验功力的环节。递推关系式的本质是当前状态是从哪些更小的状态“走”过来的。比如经典的走楼梯问题一次可以走1级或2级求走到第 n 级台阶有多少种走法。你想想要走到第 n 级最后一步只能是从 n-1 级跨1级上来或者从 n-2 级跨2级上来所以dp[n] dp[n-1] dp[n-2]。这个思路反复训练之后会变成肌肉记忆盯住“最后一步”永远问自己最后一步有哪些可能。再比如二维网格路径计数从左上角到右下角只能向右或向下走求路径总数。对于格子(i,j)你只能从上面的格子(i-1,j)向下走一步到达或者从左边的格子(i,j-1)向右走一步到达所以dp[i][j] dp[i-1][j] dp[i][j-1]。还是同一个套路。3.3 第三步定边界条件把递推的“地基”打结实边界条件就是递推的起点没有起点递推根本推不动。这是新手最容易忽略的地方——不少人关系式写得很顺一运行就报错或者算出来是错数问题十有八九出在边界上。还是走楼梯的例子dp[1] 1只有1级台阶只能走1步上去dp[2] 2可以两次走1级也可以一次走2级。有了这两个初始值dp[3] dp[2] dp[1] 3然后一路推下去。边界条件的经验法则是先把最小的几个值手算出来再写代码。n0, n1, n2这些特殊值必须单独定义因为它们往往不满足递推公式的形态。比如dp[2] dp[1] dp[0]如果dp[0]没定义那dp[2]101显然是错的——这里严格来说dp[0]按“从0级走到0级”只有一种空走法所以有的题解定义dp[0]1来让公式自洽但这种方法在n0本身需要返回 0 的场景会踩坑不如直接手动给出前几个值稳当。3.4 第四步定计算顺序确保算当前项时依赖项都已知递推必须保证计算某个状态时它依赖的状态全部已经算出来了。这个顺序通常就是“按编号从小到大”一维问题或者“从上到下、从左到右”二维问题。如果你顺着写了半天发现某个赋值语句还依赖一个没算过的值那你就是顺序写反了——这种情况在二维递推里最容易出线新手一天能碰十次。注意负数下标是大忌。写dp[i-1]时i至少要从 1 开始dp[i-2]时i必须从 2 开始。代码里最省心的方法是把dp数组开大一点下标 0 当作哨兵位从 1 开始用真实数据从 2 开始跑递推循环这样所有下标访问都安全。4. 三类高频递推模板照着写就能对4.1 一维线性递推斐波那契、跳台阶、铺瓷砖一维线性递推的特征是第 n 项只和前面固定几项有关而且关系是线性的。这类题最容易识别也最适合练手。铺瓷砖问题很有代表性用1x2的砖铺满2xn的地板求铺法总数。你想想最后一块砖怎么放要么竖着放一块剩下2x(n-1)的区域要么横着放两块叠在一起剩下2x(n-2)的区域。于是dp[n] dp[n-1] dp[n-2]。看出门道没和台阶问题一模一样只是换了个场景描述本质上还是斐波那契。我再补充一个带变形的递推让它有点新意一次可以跳1级、2级或者3级台阶求跳到第 n 级的方案数。这次最后一步有三种来源dp[n] dp[n-1] dp[n-2] dp[n-3]边界条件是dp[1]1, dp[2]2, dp[3]4。简单推一下就能验算。4.2 二维递推杨辉三角、网格路径、最小代价路径二维递推的关系式通常涉及两个维度的推进代码就是双重循环。很多动态规划入门题的第一版解法就是二维递推值得花时间吃透。杨辉三角是最直观的二维递推C(n,k) C(n-1,k-1) C(n-1,k)边界是每行首尾都是1。它同时还是组合数计算的来源后面学概率DP时还会碰到它。网格路径问题更接近实际场景。给定一个m x n网格每个格子里有一个非负代价求从左上角到右下角经过路径的最小代价每次只能向右或向下走。状态定义dp[i][j]表示走到(i,j)的最小代价那么转移就是dp[i][j] min(dp[i-1][j], dp[i][j-1]) grid[i][j]。第一行只能从左往右累加第一列只能从上往下累加这就是边界条件。写这种二次循环时我习惯先处理边界行/列再跑内部双循环。不然循环体里一堆if i 0 or j 0的特殊判断看得人头大。4.3 空间压缩技巧从二维数组到两个滚动变量很多二维递推其实只用了dp[i-1][j]和dp[i][j-1]这两个“邻近状态”根本不用把整个二维表都存下来。用滚动数组的方式空间能直接降到 O(m) 甚至 O(1)。以网格最小代价问题为例你只需要保存当前行的数据即可def minPathSum(grid): m, n len(grid), len(grid[0]) dp [0] * n for i in range(m): for j in range(n): if i 0 and j 0: dp[j] grid[0][0] elif i 0: dp[j] dp[j-1] grid[i][j] elif j 0: dp[j] dp[j] grid[i][j] else: dp[j] min(dp[j], dp[j-1]) grid[i][j] return dp[n-1]这里的核心理解点是dp[j]在更新之前存的是上一轮循环也就是上一行的第 j 列值所以dp[j]天然等于旧的dp[i-1][j]而dp[j-1]在当前循环里已经更新过了所以它等于新的dp[i][j-1]。一箭双雕空间省下一大截。我第一次接触这个技巧时很懵后来自己拿张纸模拟了一遍数据流才彻底明白。建议你看不懂代码时也照着样例手动跑一遍循环理解会扎实很多。5. 递推优化的“三板斧”面试和竞赛都用得上5.1 空间优化滚动数组到底怎么滚前面已经提了滚动数组这里再补充一个更极端的场景当你只需要dp[n-1]和dp[n-2]时连数组都不用开两个变量就够了。斐波那契的循环解法就是典型a, b b, a b这两行赋值本质上就是滚动数组的极致形态。但要提醒一句不是所有递推都能做空间压缩。如果递推关系依赖的是dp[i-2]这种跨两个位置的状态滚动窗口就至少要保留3个变量如果依赖的是任意位置的状态比如某些区间DP滚动数组基本没用。优化之前先数清楚依赖关系数错了就是数据错乱。5.2 时间优化矩阵快速幂把复杂度降到 O(logn)当 n 大到 10 的 18 次方这种量级普通循环递推也扛不住了这时得用矩阵快速幂。思路是这样斐波那契递推可以写成矩阵形式。[F(n), F(n-1)] ^ T [[1,1],[1,0]] * [F(n-1), F(n-2)] ^ T然后用快速幂对标量乘法一样计算矩阵的幂复杂度直接从 O(n) 降到 O(logn)。核心代码也不复杂def mat_mul(A, B): return [[sum(A[i][k] * B[k][j] for k in range(2)) for j in range(2)] for i in range(2)] def mat_pow(M, n): res [[1,0],[0,1]] while n: if n 1: res mat_mul(res, M) M mat_mul(M, M) n 1 return res def fib_matrix(n): if n 2: return 1 M [[1,1],[1,0]] res mat_pow(M, n-2) return res[0][0] res[0][1]这个方法看着高大上但核心逻辑和普通快速幂一模一样就是“指数二进制拆分 迭代累乘”。如果你已经掌握了普通快速幂矩阵快速幂唯一的麻烦就是矩阵乘法本身多写两遍就能熟悉。5.3 取模处理大数递推的第一现场几乎所有递推题都有一个默认设定答案可能非常大要对某个数取模常见的是10^97。关键问题是取模应该在什么时候做答案是每次加法运算之后立刻取模别等最后。原因很简单Python 的大整数虽然不怕溢出但运算速度会随数字位数增长而变慢C 的 int 和 long long 直接溢出就不是变慢的问题是算错的问题。在10^97这个模数下两个模数相加最大是(10^96)*2远没超过 long long 范围所以每步取模安全、稳当、速度快。还有一个细节模负数。有些递推关系里会出现减法比如dp[i] (dp[i-1] - dp[i-2] mod) % mod。为什么一定要加一个 mod因为dp[i-1] - dp[i-2]可能是负数C 里负数取模的结果也是负数会让数组下标变负。加 mod 再取模保证结果非负这是老手都会注意的细节。6. 三道真题拆解从读题到写出递推式6.1 上台阶问题含变体原题一个人上楼梯一次可以走1级或2级问走到第 n 级有多少种走法。这个题前面分析过不再重复。但我想提一个变体如果一次可以走1级、2级或3级就走 3 阶递推。如果想从测试角度验算n4 时答案应该是dp[3] dp[2] dp[1] 4 2 1 7你可以自己列一下 4 级台阶的所有走法数出来确实是7。这种“手算小样例验算”的习惯我强烈建议每个人都养成。6.2 数字三角形最大路径和输入一个数字三角形从顶部出发每次可以向左下或右下移动求到底部的最大路径和。状态定义dp[i][j]表示从三角形顶部走到第 i 行第 j 列的最大和转移就是dp[i][j] max(dp[i-1][j-1], dp[i-1][j]) triangle[i][j]。边界条件在每行的首尾需要特殊处理首列只可能从上一行首列下来末列只可能从上一行列过来。最后在最后一行里取最大值就是答案。这道题的价值在于训练“三角形的存储方式和普通矩阵不一样”的意识。实际输入通常是triangle [[2], [3,4], [6,5,7], [4,1,8,3]]这种列表的列表下标关系要自己理清。很多人在纸上画、在代码里写完全对不上号根因就是没把行和列的逻辑理顺。6.3 斐波那契的三种实现对比我经常拿这道题给学生做对比实验因为同样一个数列三种写法复杂度天差地别递归 O(2^n)、循环递推 O(n)、矩阵快速幂 O(logn)。我量化一下数据n100时递归已经卡到没法看n10^6时循环递推依然飞快n10^18时矩阵快速幂依然稳妥。这三种方案的选型完全取决于 n 的规模——如果你不知道 n 的上限写代码之前先问清楚不然白干。方法时间复杂度空间复杂度适用规模朴素递归O(2^n)O(n) 栈深度n 30循环递推O(n)O(1) 或 O(n)n 10^7矩阵快速幂O(logn)O(1)n 10^18这张表我建议你存下来后面刷算法题时经常用得上。7. 实战踩坑实录递推代码最常见的五个 bug7.1 边界条件多写了或少写了dp[1]、dp[2]这些初始值一旦写错后面全盘皆错。最坑的是有时候边界正确但代码从i2开始循环时把dp[1]覆盖了这类问题跑一个n1或者n2的小样例就能抓出来。我的习惯是第一遍写完代码先测试数组长度为 1、2、3 的基本用例再跑大用例。7.2 取模时机不对有次我图省事想着最后统一取模一次结果中间某个值的数量级已经到了几千位程序卡到崩溃。从那以后我的规矩就是递推循环内每一次加法结束立刻取模。这个习惯会让你少流很多眼泪。7.3 数组下标越界二维递推里dp[i-1][j]当i0时越界。处理方法前面提过单独处理边界行和边界列。这里特别提醒Python 里负数下标不报错它访问的是数组末尾元素所以Python 程序里出现“没有报错但结果错了”先排查是不是下标变成了负数——这个坑比越界崩溃更隐蔽难查十倍。7.4 循环方向搞反老老实实从前往后循环的人和直接从后往前循环的人为了所谓的“刷题感觉”写的不是一个东西。递推必须严格遵循拓扑顺序先算小的再算大的先算左上再算右下。你要是从大到小推还推对了那只能说明你的关系式恰好是对称的换个题立刻原形毕露。7.5 用递归思维硬写递推循环有人递归写习惯了转递推时总想着“把当前状态拆回下一层”结果循环体里写了一堆没用的小函数调用复杂度和递归一样爆炸。递推的正确姿势是“用已知状态去更新未知状态”你要盯着循环变量怎么一步步变大而不是盯着怎么拆。8. 递推、动态规划、状态机它们其实是一条线很多初学者分不清递推和动态规划的边界我可以给你一个明确的判断递推是动态规划的实现手段动态规划还有“决策”这个维度。当递推关系式里每次不是直接累加、而是需要取 max 取 min 做选择时它就升级成动态规划了。所以你把递推学扎实了动态规划的一半你已经掌握了剩下的“状态定义 状态转移方程 优化”本来也是从递推四步法延伸出来的。概率DP和马尔可夫链里的状态转移矩阵本质上也还是递推把“当前状态概率”表示为“上一状态概率”的线性组合再加上转移矩阵。所以别把递推当小技巧看它是很多高级算法的“地基”。如果你后面学组合数学会发现很多组合恒等式都能用递推导出学图论里的最短路Bellman-Ford 算法每次松弛本质就是在做一次递推更新。一口吃不成胖子但你先把“递推”这口吃透了后面所有依赖它的知识学起来都会顺很多。9. 一道配套练习跳台阶问题的反向思考题为了帮你检验自己到底吃透了递推我给一道稍微变形的题目你试试能不能独立推出来。题目描述一只青蛙一次可以跳上1级台阶也可以跳上2级台阶求该青蛙跳上一个 n 级台阶总共有多少种跳法。但如果加了限制条件第 k 级台阶有障碍、不能踩问方案数。思路提示递推仍然是dp[i] dp[i-1] dp[i-2]但当i k时强制dp[k] 0。这一步就是“在递推循环里加一个 if 拦截”正好考察你是否理解了递推每项都必须从左到右逐个计算。这类带限制条件的递推题常出现在面试的“图穷匕见”环节前面的基础题是热身这个变体才是真正考察你理解深度的题目。能推出来并讲清楚为什么递推这块就算真入门了。