听到“一本通1196”这个名字，很多搞信息学竞赛的同学应该会心一笑。这是《信息学奥赛一本通》递推算法章节里非常经典的一道入门题——“踩台阶”，题号1196。别看它题目短、背景简单，很多新手在这道题上栽的跟头其实不少。有的同学背下了代码却说不清递推式怎么来的，有的同学第一次写直接递归导致超时，还有人被“样例过了但测评WA”折腾到怀疑人生。
这篇文章我就把这道题彻底掰开揉碎讲一遍。包括题目到底在考什么、递推关系是怎么一步步想出来的、初级代码和进阶写法有什么区别，以及我当年带学生时总结出来的一系列踩坑记录。不管你是刚开始学递推的竞赛新手，还是带学生的教练老师，这篇文章应该都能给你一些参考。
1. 题面拆解：这题到底在问什么
先看看原题描述。题目大意是这样的：有一级、二级、三级……一共N级台阶，你从第0级开始往上走，每一步可以跨1级，也可以跨2级。问走到第N级台阶，一共有多少种不同的走法。
很多同学第一次看到这个题，第一反应是“这不就是斐波那契数列吗”，这句话对，但如果没有理解为什么是斐波那契，代码抄过去也容易出问题。
我们先用最笨的办法列一下：
- N=1时，只能一步跨1级，走法数是1。
- N=2时，可以1+1，也可以直接一步跨2级，走法数是2。
- N=3时，可以1+1+1，可以1+2，可以2+1，走法数是3。
- N=4时，1+1+1+1、1+1+2、1+2+1、2+1+1、2+2，走法数是5。
1、2、3、5……这个序列非常有规律，每一项都是前两项之和。但要注意，第4项的5其实从纯枚举角度已经有点绕了，再往后手算就容易漏。所以这道题的核心价值，不是让你去枚举，而是让你建立“用数学关系描述计数问题”的思维。
这里的递推关系隐藏在一个很简单的逻辑里，走到第N级台阶，最后一步只有两种可能：
- 最后一步跨了1级，那之前一定站在第N-1级台阶上；
- 最后一步跨了2级，那之前一定站在第N-2级台阶上。
于是到达第N级的总走法数，就等于到达第N-1级的走法数加上到达第N-2级的走法数。
这个推导过程，我觉得比代码本身重要得多。考试也好、平时刷题也好，递推题的核心永远是“这个关系式到底是怎么来的”，代码只是把关系式翻译成机器语言。
提示：这道题与斐波那契数列高度同构（只是初值略有不同），但千万不要背斐波那契模板就完事。题目考察的是你能不能自己抽象出“最后一步倒推”这个递推思想，而不是考察你背模板的能力。
2. 代码实现：从递归到递推的完整演进
对于这道题，最直观的写法是递归。很多同学第一次写出来的代码长这样：
#include <iostream> using namespace std; int f(int n) { if (n == 1) return 1; if (n == 2) return 2; return f(n - 1) + f(n - 2); } int main() { int n; cin >> n; cout << f(n) << endl; return 0; }这段代码在N很小的时候能跑出正确结果。但“能跑出结果”和“这道题真的做对了”是两回事。递归版本的f(n)每次都会去重复计算大量子问题，画一下调用树就明白了：要求f(10)，先算f(9)和f(8)；算f(9)的时候又算了一遍f(8)和f(7)。随着N变大，重复计算的次数呈爆炸式增长，时间复杂度是O(2^N)级别的。
虽然一本通原题里N通常不会给得太大（一般小于30），递归也许能过，但竞赛考的是算法素养，养成用递推解决问题的习惯非常重要，万一数据范围放大到N=1000，递归直接原地爆炸。
标准解法是正着推，从已知推到未知，用数组保存每一步计算结果，每个子问题只计算一次，时间复杂度O(N)，空间复杂度O(N)。代码可以这样写：
#include <iostream> using namespace std; int main() { int n; cin >> n; long long f[100] = {0}; // 用long long，后面会讲为什么 f[1] = 1; f[2] = 2; for (int i = 3; i <= n; i++) { f[i] = f[i - 1] + f[i - 2]; } cout << f[n] << endl; return 0; }这段代码干了一件很重要的事：它把递归里的“自顶向下”调整成了“自底向上”。先算小的，再逐步推出大的，这就是递推和递归最本质的区别。递推本质上是用空间换时间，用数组记录中间状态，避免重复劳动。
其实还可以进一步优化空间。既然f[i]只依赖前两个值，那就不需要开数组了，直接用三个变量滚动更新：
#include <iostream> using namespace std; int main() { int n; cin >> n; long long a = 1; // f(1) long long b = 2; // f(2) long long c; if (n == 1) { cout << a << endl; return 0; } for (int i = 3; i <= n; i++) { c = a + b; a = b; b = c; } cout << b << endl; return 0; }这段代码的好处是空间复杂度降到了O(1)，尤其当N很大的时候，节省内存的效果很明显。虽然这道题用不上这个优化，但养成“能省则省”的习惯对后面学习动态规划很有帮助。
我个人的建议是：初学者先老老实实写数组版递推，确保理解“数组下标对应台阶数，数组值对应走法数”。等彻底搞懂了，再尝试滚动变量版本，这能帮你加深对“状态只依赖前序状态”这个特性的理解。
3. 数据边界之坑：int会炸，数组要开够
这个题有一个特别容易踩的坑——数据类型。我第一次带学生做题的时候，班里有个同学用int定义数组，样例跑得好好的，结果交上去WA了一片。他一直没搞明白原因，后来我在他机器上把N改成40跑了一遍，输出变成了负数，他当场就愣住了。
原因其实很简单：台阶走法数的增长速度是指数级的。斐波那契数列第46项就已经超过2^31-1，也就是int的表示上限。一旦溢出，整数就会回绕变成负数，这就是那个同学WA的真相。
所以类型选择要慎重。一本通原题虽然N通常给的不大，但建议直接用long long，它的上限是2^63-1，能覆盖到第92项左右，对本道题来说非常充裕。如果哪天真遇到出题人把N出到100，那就连long long都不够用了，需要上大数高精度加法，不过那就超出这道题的范围了，属于后面高精度专题的内容。
还有数组大小的坑。我见过不少同学提交的代码是int f[30]，然后N输入20，没问题；但如果数据范围稍微调一下，N变成了35，数组越界，后果完全不可预知。虽然一本通原题的数据比较温柔，但养成看数据范围写代码的习惯，是竞赛生的基本素养。
注意：不管你用数组版还是滚动变量版，都要先明确题目的数据范围再决定类型。稳妥起见的组合是
long long+ 数组开大到110，足够应对绝大多数递推题。
再补充一个输入输出的细节。这题输入是一个整数N，输出是一个整数走法数。大多评测系统对行末空格和文末换行不敏感，但不要因此养成乱输出的习惯。一律按题目要求来：只输出数字，结尾换行。有些同学喜欢在输出后面跟一堆调试信息，调试的时候随便，提交之前务必删干净。
4. 踩坑实录：我见过的各种离奇WA原因
在带学生的过程中，我把这道题相关的WA原因汇总过一遍。把这些写出来，是希望准备做这道题的同学少走弯路。
第一个高频问题：初始值设置错误。有人写了f[0] = 1; f[1] = 1;，这是斐波那契数列的写法。对于踩台阶这道题来说也可以这样定义，因为第0级到第1级有一种走法，第0级到第0级也可以理解成一种“原地不动”的方案，但从教学角度讲，大多数教材默认从f[1]=1, f[2]=2开始，最直观，不容易绕晕。如果你非要用f[0]=1, f[1]=1，递推式也能成立，但初学者特别容易在N=0这种边界情况下出错，不如直接用教学版初值。
第二个高频问题：递归写得太深导致栈溢出。有些数据范围较大的变体题，直接用递归写法会爆栈。踩台阶这道题原版N不大，递归还勉强能过，但如果把这个题改成一本题库里的“上台阶”加强版，N能到几百几千，递归直接崩溃。这也是我反复强调要用递推不用递归的原因。
第三个问题比较隐蔽：多组测试数据。有一些在线题库会把“踩台阶”改成多组输入，直到读到某个结束标志才停止。如果没注意输入格式，只处理一组数据，看起来样例能过，实际测评全WA。建议写代码之前，先看清楚题目到底是一组输入还是多组输入，要支持多组就把核心逻辑包在循环里，每次重新初始化数组。
第四个问题：中途取模。这个在原题里没有，但我遇到很多学生在做变式题时会自作聪明地加上mod 1000000007的取模操作。如果题目没有要求取模，你多取一步模反而会WA。先看题，再动手，不要凭经验盲写。
我整理了一张表，把常见的错误写进去，方便自查：
| 错误类型 | 具体表现 | 解决办法 |
|---|---|---|
| 数据类型溢出 | N稍大输出负数 | 使用long long |
| 数组越界 | 程序崩溃或输出随机值 | 数组按数据范围上限加余量 |
| 初值错误 | 答案固定差1或差2 | 检查f[1]、f[2]是否设置正确 |
| 忽略多组输入 | 样例能过但测评WA | 先看输入格式再写循环 |
| 多余取模 | 结果和标准答案不一致 | 按题目要求来，没要求就不取模 |
| 递归超时 | 大N跑不出结果 | 改成数组递推或滚动变量 |
5. 从踩台阶到递推思维：一类题的举一反三
这道题最大的价值，不是让你记住斐波那契的代码，而是帮你建立“递推计数”的思维模型。以后遇到很多看似完全不像的题目，本质都能化归到这个模型上。
比如换个问法：某人上楼梯，每次可以走1级或2级或3级，问走到第N级有多少种走法。递推式就变成了f[n] = f[n-1] + f[n-2] + f[n-3]，初值需要算好f[1]=1, f[2]=2, f[3]=4。
再换个问法：每次必须走偶数级台阶，或者某级台阶坏了不能踩，这时候递推关系就变得复杂些，但核心思路还是“最后一步倒推”。坏台阶的情形相当于某些状态不可达，对应到数组里就是该位置的值为0。
更有意思的变式是“升级版踩台阶”：有一只青蛙一次可以跳上1级台阶，也可以跳上2级……它还可以跳上n级。求该青蛙跳上一个n级台阶总共有多少种跳法。这个题在网上非常火，它其实是把步长选择范围从{1,2}扩展到了{1,2,...,n}。这时候递推式变成f[n] = f[n-1] + f[n-2] + ... + f[1] + 1，化简结果恰好是f[n] = 2^(n-1)，很有意思。能独立推导出这个结论的同学，对递推的理解就算入门了。
还有一道很经典的变式是“数字三角形”或者其他二维的递推计数题，比如从格子左上角走到右下角，只能向右或向下走，有多少种路径。它的递推式是dp[i][j] = dp[i-1][j] + dp[i][j-1]，本质上和踩台阶同根同源，只是把一维状态升级成二维状态。
所以在学习策略上，我强烈建议你准备一个“递推模型笔记本”。每做完一道递推题，写下三样东西：状态是什么（数组下标代表什么）、递推关系是什么（当前项怎么由前面项推出）、初值是什么（前几项手工验证）。这道1196踩台阶做完，你其实就有了第一个标准模板，后面遇到任何递推题，都可以对照这个模板去套。
再讲一个进阶方向，如果N特别大，比如N=10^18，递推的O(N)也跑不动了，这时候就要用矩阵快速幂把时间复杂度降到O(log N)。踩台阶的递推关系可以写成矩阵形式：
[f(n) ] [1 1] [f(n-1)] [f(n-1)] = [1 0] * [f(n-2)]
矩阵快速幂是后面数学专题的内容，现在不必深究，但你要有个概念：递推式理解得越深刻，后期能嫁接的高级算法就越多。
6. 实测心得：从跑通到讲明白的距离
最后聊点我自己的教学感受。这道题我前前后后给好几届学生讲过，每一届都有新的领悟。最明显的一点是：学生听懂递推式只需要五分钟，但从“听懂”到“自己能独立写出不WA的代码”，往往需要好几个小时。
这个差距主要卡在对“状态”这个概念的理解上。很多学生把f[i]当成一个普通的数组变量，没有意识到f[i]的含义是“走到第i级台阶的走法总数”。一旦理解了这一点，递推式自然就活了，代码也能和题目描述一一对应起来。
我给学生的建议是：拿到递推题之后，先不要写代码。拿出一张纸，把前5项手工算一遍，每一步都写下“为什么是这个数”。等你手工算出来的结果和题目样例一致时，再动手写代码，一次性AC的概率会大幅提升。
还有一个容易被忽略的点：测试习惯。很多同学做完题以后样例能过就觉得万事大吉，这种心态在竞赛中是致命的。至少应该自己多测几组边界数据：N=1时输出1，N=2时输出2，N=3时输出3，N=46时输出1836311903（这是long long能正确承载的一个边界值，可以当基准测试）。
如果你发现N=46输出不对，基本可以断定是数据类型的问题；如果N=5输出就是错的，那大概率是初值或者递推式写错了。
自己手算验证的方式，对新手来说最有价值的是“递推跟踪法”：假设N=5，手动模拟代码运行过程，看看每一步a、b、c三个变量的值是多少。第一次跑通这个流程后，你对递推的理解会有一个质的提升。
这道题虽然简单，但它是递推章节的第一块基石。代码没几行，逻辑也不复杂，但它背后涉及的思维转变——从“暴力枚举所有走法”到“利用状态转移关系计数”——是整个信息学竞赛解题思维的重要跨越。把这个坎迈过去，后面的动态规划、记忆化搜索、最短路等一大片内容，学起来都会顺很多。
