听到“一本通1196”这个名字很多搞信息学竞赛的同学应该会心一笑。这是《信息学奥赛一本通》递推算法章节里非常经典的一道入门题——“踩台阶”题号1196。别看它题目短、背景简单很多新手在这道题上栽的跟头其实不少。有的同学背下了代码却说不清递推式怎么来的有的同学第一次写直接递归导致超时还有人被“样例过了但测评WA”折腾到怀疑人生。这篇文章我就把这道题彻底掰开揉碎讲一遍。包括题目到底在考什么、递推关系是怎么一步步想出来的、初级代码和进阶写法有什么区别以及我当年带学生时总结出来的一系列踩坑记录。不管你是刚开始学递推的竞赛新手还是带学生的教练老师这篇文章应该都能给你一些参考。1. 题面拆解这题到底在问什么先看看原题描述。题目大意是这样的有一级、二级、三级……一共N级台阶你从第0级开始往上走每一步可以跨1级也可以跨2级。问走到第N级台阶一共有多少种不同的走法。很多同学第一次看到这个题第一反应是“这不就是斐波那契数列吗”这句话对但如果没有理解为什么是斐波那契代码抄过去也容易出问题。我们先用最笨的办法列一下N1时只能一步跨1级走法数是1。N2时可以11也可以直接一步跨2级走法数是2。N3时可以111可以12可以21走法数是3。N4时1111、112、121、211、22走法数是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递归也许能过但竞赛考的是算法素养养成用递推解决问题的习惯非常重要万一数据范围放大到N1000递归直接原地爆炸。标准解法是正着推从已知推到未知用数组保存每一步计算结果每个子问题只计算一次时间复杂度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递推式也能成立但初学者特别容易在N0这种边界情况下出错不如直接用教学版初值。第二个高频问题递归写得太深导致栈溢出。有些数据范围较大的变体题直接用递归写法会爆栈。踩台阶这道题原版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特别大比如N10^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的概率会大幅提升。还有一个容易被忽略的点测试习惯。很多同学做完题以后样例能过就觉得万事大吉这种心态在竞赛中是致命的。至少应该自己多测几组边界数据N1时输出1N2时输出2N3时输出3N46时输出1836311903这是long long能正确承载的一个边界值可以当基准测试。如果你发现N46输出不对基本可以断定是数据类型的问题如果N5输出就是错的那大概率是初值或者递推式写错了。自己手算验证的方式对新手来说最有价值的是“递推跟踪法”假设N5手动模拟代码运行过程看看每一步a、b、c三个变量的值是多少。第一次跑通这个流程后你对递推的理解会有一个质的提升。这道题虽然简单但它是递推章节的第一块基石。代码没几行逻辑也不复杂但它背后涉及的思维转变——从“暴力枚举所有走法”到“利用状态转移关系计数”——是整个信息学竞赛解题思维的重要跨越。把这个坎迈过去后面的动态规划、记忆化搜索、最短路等一大片内容学起来都会顺很多。