如果你刷过几道和计数有关的算法题一定遇到过这种场面题目让你数方案数数据规模给到几百万甚至上千万你画了半天草稿最后列出一个式子一跑就过。这个式子就是递推式。我从开始学算法到现在一直觉得递推是被低估得最厉害的基础专题——它不需要树状数组不需要图论门槛低到一句话能讲完但真正能把递推式列对、列全、列得不重不漏的人其实很少。这篇不是把课本上那几道例题念一遍而是把我平时做题时怎么找递推、怎么验证递推、怎么把递推写成不超时也不溢出的程序再连带踩过的坑一次性讲清楚。内容从入门到进阶都有适合刚学算法的同学也适合备赛前想系统整理一遍基础专题的选手。读完你至少能建立起一个判断拿到一道计数题递推能不能做、递推式怎么来、写出来怎么排查错误。1. 递推到底在推什么从“由前向后”说起1.1 递推式的三要素初值、关系式、迭代方向很多人以为递推就是“a_n a_{n-1} 1”这种带下标的公式其实这只是递推关系式完整的递推问题必须有三个东西初值、关系式、迭代方向。缺一个程序就跑不对。初值解决的是“从哪开始算”。比如排队报数第一个人报“1”后面每个人报“前一个数加1”那么从第一个人往后推一百个人的报数都能算出来。但如果第一个人报几你不知道整个队列的报数全是空中楼阁。递推里的 f[0]、f[1]、f[2]就是那个“第一个人”。关系式解决的是“怎么从前面的状态推出当前状态”。它要满足一个基本要求计算第 i 项时它依赖的所有项都已经算好了。这就是迭代方向的意义。大部分递推是从小到大下标递增着推极少数的题目是从大到小推或者按某种特殊顺序推但核心原则只有一个——依赖关系必须已经满足。我见过很多新手在递推上翻车不是因为找不到公式而是不知道公式还需要初值。比如斐波那契数列f[n] f[n-1] f[n-2] 谁都会写但 f[0] 到底等于 0 还是 1题目让求第几项如果题目说“第 1 项为 1第 2 项为 1”你下标从 0 开始还是从 1 开始这些细节不定清楚代码跑出来边界必挂。1.2 从实际问题到递推式两种最常用的切法拿到一道计数题怎么从题面抽象出递推关系我用得最多的就两个动作。第一个动作考虑第一步或者最后一步有哪几种走法按选择分类。拿爬楼梯举例一次能上 1 阶或 2 阶问上到第 n 阶有多少种走法。我从最后一步看到第 n 阶要么是从第 n-1 阶跨上来的要么是从第 n-2 阶直接跨上来的。于是 f[n] f[n-1] f[n-2]。这两种情况是互斥的因为最后一步不可能既是 1 阶又是 2 阶同时它们覆盖了所有走法因为最后一步只可能是这两种之一。这就是“不重不漏”的来源。第二个动作插入法。这类题目多出现在排列、集合、字符串相关的计数里它的思路是假设我已经把前 n-1 个对象处理好了现在第 n 个对象加入看看它有多少种方式和前面已经形成的结构互动。后面讲错排公式时你会看到这个动作的完整版。我个人建议看到递推式不要急着背而是脑子里反复训练“要么……要么……”的分情况讨论。一旦你能把题目里的计数过程拆成几个更小规模的、结构相同的计数过程递推式基本上就自己浮出来了。1.3 先手算前几项再写代码我写递推题有个固定习惯先手算 f[0]、f[1]、f[2]、f[3]算完再列递推式最后才写代码。这个过程看起来多余实际上能帮你避掉八成以上的错误。手算最大的作用是验证初值。很多递推式里会出现 f[0] 1 这种约定比如“空矩形的铺法算 1 种”“空序列合法算 1 种”。不理解的人会把 f[0] 设成 0然后从 f[2] 开始特判代码瞬间变得又长又容易错。其实你只要把 n 1、2 代回递推式看看等号两边是否成立初值的设置是否合理立刻就能发现。举个例子后面要写的铺瓷砖题递推式是 f[n] f[n-1] 2f[n-2]。如果我把 f[0] 设成 0、f[1] 设成 1那么 f[2] f[1] 2f[0] 1但实际手动枚举一下 2×2 的矩形能铺出 3 种方案。这一代就能发现 f[0] 设错了改成 f[0]1 之后 f[2]3一切自洽。这种自查本事是递推题做得又快又稳的关键之一。2. 三类高频递推模型看懂题目套路2.1 线性递推斐波那契家族斐波那契数列是整个递推专题里出场率最高的模型递推式是 f[n] f[n-1] f[n-2]。爬楼梯、兔子繁殖、铺设 2×n 矩形地板、简单路径计数本质上都是这个模型区别只在初值的写法。这类题目的特点是当前状态只依赖前面一两个状态转移方向和顺序固定写起来非常机械。但正因为机械很多人反而会栽在“题目让求第几项”这种问题上。有些题从第 0 项开始算有些从第 1 项开始算有些把“一步都不走”也当作一种走法这直接决定了 f[0] 是 1 还是 0。我的经验是做题时先在注释里把状态定义写清楚。状态定义里必须包含“下标从几开始”“f[i] 表示什么规模的问题”“边界条件是什么”。写完递推式再看一眼如果状态定义和递推式互相矛盾一眼就能看出来省得调半天 bug 才发现是定义和公式对不上。2.2 分治递推汉诺塔移动次数汉诺塔问题带出了一个经典递推式f[n] 2*f[n-1] 1。它的推导过程很有代表性也很容易让人混淆。要把 n 个盘子从 A 柱移到 C 柱分三步先把上面 n-1 个盘子从 A 移到 B需要 f[n-1] 次再把最大的盘子从 A 移到 C需要 1 次最后把 B 上的 n-1 个盘子移到 C又需要 f[n-1] 次。于是 f[n] 2*f[n-1] 1初值 f[1] 1。这个递推式里出现了“2 倍”它表示问题被拆成了两个规模相同但相互独立的子问题而不是说时间复杂度翻倍。事实上展开之后 f[n] 2^n - 1指数增长。这个例子告诉我们递推式并不是只能用来做计数它也能用来描述操作次数、程序步数、资源消耗等一切带有“规模递进”关系的东西。我经常跟人强调汉诺塔是理解“分治结构下的递推”最好的入门题因为它把大问题拆成小问题的路径非常清晰每一步都可以在真实世界里验证不像有些抽象计数题推了半天也不知道自己分类对不对。2.3 集合重排递推错排公式错排公式是递推题里最容易考到、也最容易让人记混的一个。它的定义是n 个元素排列要求每个元素都不在自己原来的位置上问有多少种排列。记作 D[n]。初值是 D[1] 0D[2] 1。递推式是 D[n] (n-1) * (D[n-1] D[n-2])。这个式子背下来不难难的是理解它怎么来的。推导过程特别能体现“插入法”的威力。考虑第 n 个元素它不能放在位置 n所以它可以放在位置 1 到 n-1 中的任意一个共 n-1 种选择。假设它放在了位置 k现在分两种情况第一种原来在位置 k 的那个元素刚好也放到位置 n 去。这样元素 n 和元素 k 互换了位置剩下 n-2 个元素还是错排问题方案数是 D[n-2]。第二种原来在位置 k 的那个元素不去位置 n。那我们就强行要求除了元素 n 之外剩下的 n-1 个元素分别在位置 1 到 n-1 上排列其中元素 k 既不能回位置 k也不能去位置 n。这本质上就是一个 n-1 个元素的错排问题方案数是 D[n-1]。两种情况加起来乘以 n-1就是 D[n] (n-1) * (D[n-1] D[n-2])。这个推导过程里有几个容易想不通的点第二种情况为什么是 D[n-1]因为“元素 k 不能放到位置 n”这个限制相当于把位置 n 视为元素 k 的“新家”而元素 k 原来的位置 k 又是它不能回去的位置所以剩下的 n-1 个元素谁也不能呆在自己的“对应位置”上这就是一个标准的错排。理解到这个层面公式就不可能记错。2.4 卡特兰数递推式里的“卷和”卡特兰数是另一类高频递推模型递推式长这样C[0] 1C[n] Σ_{i0}^{n-1} C[i] * C[n-1-i]。它的特点是当前状态是所有 i 从 0 到 n-1 的乘积之和数学上叫卷积形式。卡特兰数长得很“吓人”但出现的场景特别多n 对括号的合法序列数量、n 个节点能组成的二叉树形态数、凸 n2 边形的三角剖分数、出栈序列的数量全都归它管。如果你在递推题里发现式子带着 Σ而且每一项都是两个小规模状态的乘积就要条件反射地想到卡特兰数。这类递推式的时间复杂度是 O(n²)因为每一项都要做一轮求和。n 在几千以内直接算没问题n 到 1e6 就必须用通项公式或其他优化手段了。不过那属于进阶内容初学阶段先把“卷积型递推”这个模型认出来知道它是哪一类问题就够了。3. 从递推式到程序一道铺瓷砖题的完整实操3.1 题目描述与手推前几项我们把上面的模型组合一下做一道稍微综合一点的题目用三种瓷砖铺满一个 2×n 的矩形地面。瓷砖有三种一块 1×2 的竖砖恰好覆盖一列的两格两块 2×1 的横砖分别放在上下两行一起覆盖两列一块 2×2 的方砖直接覆盖两列。问有多少种不同的铺法。这个题我第一次做的时候直接上手写代码结果样例都过不了。后来老老实实手推n1地面是 2×1只能放一块竖砖f[1]1。n2地面是 2×2。可以放两块竖砖也可以放两块横砖还可以放一块 2×2 方砖共 3 种f[2]3。n3按照后面要写的递推式f[3]f[2]2*f[1]325。手数也能数出来第一列放竖砖时剩下 2×2 有 3 种前两列放两块横砖时剩下 2×1 有 1 种前两列放方砖时剩下 2×1 还有 1 种总计 5 种。手推前几项之后规律已经出来了f[n] f[n-1] 2*f[n-2]。这个式子看着简单但它的分类逻辑值得细讲。3.2 建立递推式时如何做到不重不漏铺瓷砖题最容易犯的错误是分类重叠。比如有人说“最后一列放竖砖剩下 n-1 列随便铺最后两列放横砖或方砖剩下 n-2 列随便铺”这样直接得到 f[n] f[n-1] 2*f[n-2]看起来没错但有些人会越想越不对“方砖和两块横砖都占两列这不重了吗”其实不重。方砖和横砖是两种不同的铺法它们占用两列的方式不同在计数时必须分别算所以系数是 2。不重不漏的关键在于我们从最左侧开始分类看左边第一列是怎么被覆盖的。第一列只有三种可能一块竖砖覆盖上下两格、两块横砖分别伸到第二列、一块方砖覆盖前两列。这三种方案互斥因为第一列第一格的情况不可能同时属于两种方案同时它们覆盖了所有铺法因为第一格总要被某种砖覆盖。如果你从左往右分类还是从右往左分类其实都行但一定要固定一个边界不要混着来。比如你左边用“第一列”分类右边又用“最后一列”分类中间就会漏掉或者重复某些情况。固定“最左边第一个未被覆盖的格子”作为分类基准是避免错乱的好办法。还有一个细节横砖为什么要成对出现因为单放一块 2×1 横砖只占一行的两列它所在列的另一行必然空着这个空格必须由另一块横砖或者方砖来补而一旦要补就会形成至少两列的区域。所以横砖总是“上下两行各一块”成对出现这就是 2*f[n-2] 里那个 2 的物理意义。3.3 程序实现与边界处理递推式确定后实现就很简单。C版本#include bits/stdc.h using namespace std; const int MOD 1000000007; int main() { int n; cin n; vectorlong long f(n 1, 0); f[0] 1; f[1] 1; for (int i 2; i n; i) { f[i] (f[i - 1] 2LL * f[i - 2]) % MOD; } cout f[n] endl; return 0; }Python版本MOD 10**9 7 n int(input()) f [0] * (n 1) f[0] 1 f[1] 1 for i in range(2, n 1): f[i] (f[i - 1] 2 * f[i - 2]) % MOD print(f[n])边界处理有几个关键点。第一f[0] 必须设成 1。虽然“0 列地面”看起来没有意义但它是让递推式在 n2 时成立的必要条件。如果不设成 1f[2] 算出来只有 1错得离谱。第二数组下标从 0 到 n所以开 n1 的长度访问 f[n] 不会越界。第三循环从 2 开始因为 f[0] 和 f[1] 是初值不需要通过递推得到。3.4 空间优化与取模细节上面的实现是 O(n) 时间和 O(n) 空间。如果 n 到了 1e7开一个 1e7 的 long long 数组大概 80MB很多题目的内存限制是 256MB勉强能过但如果题目再给紧一点或者变化版的状态更多就得考虑滚动数组。滚动数组的思想是既然 f[i] 只依赖 f[i-1] 和 f[i-2]那我只保留两个变量就够了不必把整个数组都存下来。long long a 1, b 1; // a f[0], b f[1] for (int i 2; i n; i) { long long c (b 2LL * a) % MOD; a b; b c; } cout b endl;取模也是递推题的重灾区。很多人写完代码“忘了取模”或者只在最后取一次结果中间值早就溢出变成负数了。正确的做法是每一次转移都取模乘法也要注意类型。比如 2 * f[i-2]当 f[i-2] 接近 1e9 时2 乘一下接近 2e9int 最大才 2.147e9勉强能扛住但再多乘一个数就爆了。所以涉及乘法的中间量一律用 long long这是最稳妥的习惯。4. 递推、递归与动态规划区分与连接4.1 递推是自底向上递归是自顶向下很多初学者分不清递推和递归因为这两个词在中文里只差一个字但方向完全相反。递归是“自顶向下”的拆解。求 f[n] 的时候先假设 f[n-1] 和 f[n-2] 已经算好于是去调用自己求这两个值。这样从 n 一路往下拆直到拆到初值再一层层返回。递归写起来和数学公式很像非常直观但如果你不加记忆化它会指数级重复计算。比如裸递归求 f[50]会反复求很多很多次 f[30]、f[20]跑起来能等到你怀疑人生。递推是“自底向上”的填充。从 f[0]、f[1] 开始一步一步推到 f[n]每个值只算一次时间复杂度是 O(n)。它不直观但快而且不用递归栈不会爆栈。举个例子n 很大时递归深度可能上万C 默认栈很容易溢出递推完全没这个顾虑所以能用递推解决的问题我一般优先写递推。4.2 记忆化搜索递归形态的递推有一种折中的写法叫记忆化搜索思路就是“递归 缓存”。第一次递归算出某个状态后把它存进数组下次再遇到直接返回。从复杂度的角度看记忆化搜索和递推做的事完全一样都是“每个状态只算一次”。区别只是代码的形态递推用循环从前往后填记忆化搜索用手写递归从后往前查。有些题目的状态转移方向不直观比如依赖关系是乱序的这时候递推的循环顺序不好确定记忆化搜索反而好写——你不需要费心想顺序只需要保证“递归函数里先调用依赖的状态”。所以我的建议是能直接想清循环顺序的题目用递推写出来干净、可控状态转移方向比较奇怪的题目用记忆化搜索省心。两者本质是同一个思想不用把它们对立起来。4.3 动态规划多了一个“决策”递推和动态规划的关系更微妙。动态规划的经典要素是“状态 状态转移方程”这一点和递推完全一致。真正多出来的东西是递推通常是在做计数每一步是若干种情况相加结果是确定的而动态规划在做决策每一步会在多个候选值里取最大值或最小值转移方程里往往带着 max 或 min。所以“DP 就是带决策的递推”这个说法我认为是成立的。学会了递推再学动态规划会轻松很多因为整套分析框架你已经会了——定义状态、列转移、确定初值只是 DP 多了一个“在每个转移里比大小”的动作。反过来如果你 DP 还学不明白回头看看递推也是一种很好的补课方式。很多 DP 的“状态定义”和“转移方程”本质上都是递推式的泛化。5. 常见问题与排查技巧实录5.1 初值错最常见的一个坑递推题报错十次有八次是初值问题。f[0] 该设 1 设成 0或者 f[1] 该设 1 设成 0答案会从第 2 项开始全面偏移而且你盯着递推式看半天也看不出来因为公式本身没错。排查方法是回代。拿到递推式后把最小的几项代入看等号两边是否成立。比如 f[n] f[n-1] 2f[n-2]代入 n2 时如果等式右边是 f[1]2f[0]你就必须明确 f[0] 该是多少f[2] 的手算值才成立。这个方法几乎能解决所有初值问题因为初值不是“感觉”出来的而是让递推式自洽“倒推”出来的。5.2 下标与数组开法0-based 还是 1-based下标问题是第二个常见坑。题目说第 1 项是 1你数组却从 0 开始存循环到 n 时访问 f[n]实际上访问的是第 n1 项答案自然错。我的习惯是先在注释里写清楚“f[i] 表示规模为 i 的问题的答案下标从 0 开始f[0] 表示规模为 0 的答案”。然后代码里所有写法都围绕这个定义展开。千万不要一会儿用 0-based一会儿用 1-based。如果题目描述是“第 1 项”我可以让 f[1] 初始值循环从 2 开始只要定义一致就行。关键是定义清晰而不是强行统一成某一种。另外数组长度至少开 n2或者直接开一个较大的常量数组比如 const int MAXN 1000005; long long f[MAXN];省去动态分配的一些边界问题。5.3 分类重复或遗漏答案不是大就是小如果你代码跑出来答案总比手算的大多半是分类有重叠如果总比手算小多半是分类有遗漏。排查时回归最小规模重新画图看你的分类基准是否固定。以铺瓷砖题为例如果你一会儿按“第一列”分类一会儿按“最后一列”分类就会混。固定的做法我已经讲过找最左侧第一个未覆盖的位置看它可能被哪几种方式覆盖每种方式对应到剩余规模。还有一种情况是分类本身没错但初值设置让某种情况被算进了不应该算进的地方。这就是为什么我强烈建议先手算前几项再写代码手算结果就是你的“对照标准”。5.4 溢出与取模时机取模不是“最后做一次”的操作而是每一步转移都要做。原因很简单中间值可能已经大到溢出溢出的那一刻数据就坏了你再取模也救不回来。使用 long long 是基本操作但还要注意乘法的顺序。比如 2 * f[i-2] 中如果 f[i-2] 本身就是 int2 和它相乘时不会自动提升为 long long所以我会写成 2LL * f[i-2] 强制转类型。如果是三个数相乘更要小心尽量写成 (tmp1 % MOD) * (tmp2 % MOD) % MOD 的形式。5.5 递推太慢有哪些优化方向如果 n 不大O(n) 已经是最优了。但如果 n 到了 1e7 以上甚至 1e18就要考虑优化。第一空间优化滚动数组只保留必要的前几个状态。第二状态压缩有些递推式表面上是二维其实可以用一维表达或者用位运算压缩。第三转移优化如果递推式里带求和比如 f[i] Σ f[j] * w[i-j]直接算是 O(n²)。这类式子如果能写成“新状态 上一个辅助变量的某种更新”就可以把求和降成 O(1) 转移。你能做的是在纸上展开几项看公共部分能不能用一个变量维护。第四n 极大时的矩阵快速幂。比如斐波那契数列如果 n 是 1e18普通循环直接超时。这时可以把递推写成矩阵形式[f[n]] [1 1]^(n-1) [f[1]] [f[n-1]] [1 0] * [f[0]]矩阵快速幂能把 O(n) 降成 O(log n)。这个属于进阶玩法但理解它依赖的仍然是“递推关系可以用线性变换表示”这个视角。5.6 递推式“推不出来”怎么办我刚开始练递推时最崩溃的就是盯着题目半小时写不出式子。后来总结出一套流程分享给你。先写小规模。把 n1、2、3、4 的真实答案都手算出来。有时候答案序列一列出来规律自己就出来了。再想“第一步/最后一步”的分类。这种切法覆盖了绝大多数递推题。如果题目有某种“边界位置”优先从那里下手。如果切不出来试试“插入法”。思考第 n 个对象加入时和前面 n-1 个对象的排列/组合之间有什么关系。如果还是不行可能是状态不够。原本只考虑一维不够要加一维。比如有些铺砖题光看长度推不出来但加一维状态表示“最后一列有没有被某种特殊砖块占住”递推式立刻清晰了。最后记住平时积累模型很重要。斐波那契、错排、卡特兰这几个模型见多了看到类似结构的题目会自然联想。递推不是灵光一闪而是模型识别和分类讨论的组合拳。下面用一个速查表总结常见问题症状可能原因排查方法输出比手算小初值少了或分类遗漏回代递推式检查初值手画分类图输出比手算大分类重叠或初值多算固定分类基准检查是否重复计数n0 或 n1 崩溃数组开小或初值未定义数组多开明确 f[0]、f[1]数值溢出乘法未转 long long取模时机不对每步取模乘法用 2LL 写法超时重复计算或 n 太大滚动数组、转移优化、矩阵快速幂6. 怎么练出递推的“题感”写到这里我自己在算法学习上的一点体会也想分享一下。递推这个专题你背再多经典结论都不如自己亲手推一遍来得扎实。每次拿到递推题我给自己定一个流程先手算前五项再写分类讨论最后写代码验证。前两步看起来很慢但真正熟练以后它们反而帮你省下大量的调试时间。还有一个小技巧写递推代码时把“状态定义”用注释写在最前面。比如// f[i] 表示铺满 2*i 地面的方案数f[0]1 表示空地面算一种。这个注释不是写给别人看的是写给你自己看的。因为一旦状态定义模糊递推式十有八九是错的。每次我写完注释再回头看递推式经常能发现一些自相矛盾的地方这就是注释的价值。递推思维说白了就是“把一个复杂的计数过程拆成若干个更小但结构完全相同的计数过程”。这句话听起来简单但真正内化需要时间和题量。建议你从爬楼梯、铺瓷砖、汉诺塔、错排、卡特兰这几个经典模型入手每道题都自己推到能独立写出递推式为止。等你哪天看到计数题第一反应是“这个状态能不能由前一个状态转移过来”你的递推就算练到家了。