洛谷P1255数楼梯：动态递推与高精度加法实战解析

最近在洛谷刷题做到“P1255 数楼梯”这道题时我愣了一下。题目描述非常简单楼梯有 N 级台阶每次可以上一级或者两级问到达第 N 级一共有多少种不同的走法。很多新手看到这种题第一反应是“这不就是斐波那契吗”但真正动手提交之后才发现事情没那么简单。等你看到数据范围里 N 可以到 5000再算一下结果有多少位就会明白这道题表面考递推实际真正想让你练的是两件事状态设计以及手写高精度加法。这道题非常适合正在刷算法入门题、准备竞赛或者想检验自己高精度模板有没有写明白的人。我把它从读题到 AC 的整个思考过程完整记录下来包括递推式的推导、结果位数的估算、高精度加法的实现还有一些我实际踩过的坑。希望能帮你少走几步弯路。1. 先读懂题目数楼梯到底要我们算什么1.1 输入输出与范围解读先明确一下题目要求。输入是一个整数 N表示楼梯的级数。输出是从第 0 级走到第 N 级的不同走法数量。规则是每一步只能走 1 级或 2 级不能多也不能少。这里最容易忽略的是 N 的范围。原题里 N 最大到 5000而我第一次做的时候默认它是一个普通整数直接用long long去算结果样例过了一提交 WA 得莫名其妙。后来我才意识到这个范围就是明确提示结果不是普通整数能装得下的。你可以先把小规模情况列出来感受一下N走法总数11223345581089看到 1、2、3、5、8 这个序列熟悉的人已经认出来了这就是斐波那契数列。但 N5000 时这个数已经是一个 1000 多位的天文数字。用int、long long、甚至__int128都完全不够必须自己实现大整数运算或者使用支持大整数的语言。1.2 为什么暴力枚举走不通很多初学者会先尝试枚举所有走法。把每一步的选择记录下来比如从第 0 级开始每次递归尝试走 1 级或 2 级直到到达第 N 级统计路径数。这个思路本身没错但它是指数级复杂度。当 N 比较小比如 N10 的时候枚举完全没问题一旦 N 到了 30递归分支已经非常多到了 50 以上程序就会明显卡顿N5000 时哪怕全世界所有计算机一起算到宇宙热寂也算不完。所以这道题从一开始就注定不能暴力必须往动态规划的方向想。而动态规划的关键就是找到一个清晰的状态定义以及状态之间的转移关系。2. 从最后一步出发状态设计与递推关系2.1 状态定义到达第 i 级台阶的走法数我们定义f[i]表示从第 0 级走到第 i 级台阶的不同走法总数。现在思考一个问题要到达第 i 级最后一步是怎么走的最后的动作只有两种可能从第 i-1 级跨 1 级上来或者从第 i-2 级直接跨 2 级上来。不可能有其他方式。所以到达第 i 级的走法数就等于到达第 i-1 级的走法数加上到达第 i-2 级的走法数也就是f[i] f[i-1] f[i-2]这个递推式就是斐波那契数列的定义式。走到这里问题看起来已经解决了只需要从前往后循环计算到f[N]就行。这里我特别想强调“从最后一步倒推”这个思考方式。很多动态规划入门题难点不在于代码本身而在于你能不能建立一个不重不漏的状态转移。你可以把整个走楼梯过程想象成一段一段拼接起来的路径最后一段路必然是从某个位置出发的这个位置只可能是 i-1 或 i-2。只要把最后一步的可能性枚举完整前面的路径数自然由子问题给出。2.2 边界条件怎么定更稳边界条件是新手最容易翻车的地方。这里有两个习惯性的定义方式第一种是直接定义f[1] 1f[2] 2然后从i 3开始循环。这个方式最直观因为走到第 1 级只有一种走法走到第 2 级可以一次跨两级也可以分两步各跨一级所以是 2 种。第二种是定义f[0] 1f[1] 1从i 2开始循环。这种定义方式是很多竞赛选手更偏爱的因为它把边界统一成f[0] 1递推式从第 2 项起就自动成立。但代价是需要理解“从第 0 级到第 0 级”算 1 种走法的抽象含义。我个人建议初学者选择第一种因为它的物理含义更清晰。但要记得特判N 1和N 2的情况否则访问数组下标越界或者结果错误。如果使用第二种代码会更统一也不容易漏边界但需要你确实想明白f[0] 1的合理性。2.3 复杂度分析O(n) 为什么够用从i 3循环到i N每一步做一次加法时间复杂度是 O(N)。对于 N5000 来说这个复杂度简直微不足道。但注意这里的“加法”不是普通整数加法因为f[i]可能是一个超大的整数。如果高精度加法是用数组模拟一位一位相加那么每一次加法的代价和数字的位数有关总复杂度大约是 O(N²) 量级。N5000 时也就是大约 2500 万次单位运算在 1 秒内完全可以接受。这也是为什么这道题用最朴素的高精度写法就能过不需要额外优化到 FFT 之类的快速乘法。3. 高精度加法这道题真正的分水岭3.1 5000 级台阶的结果到底有多大我算一下这个数到底有多大。斐波那契数列的闭式公式是F(n) (φⁿ - ψⁿ) / √5其中 φ 约等于 1.618ψ 约等于 -0.618。当 n 很大时ψⁿ 这一项趋近于 0所以 F(n) 约等于 φⁿ / √5。一个数的位数可以用常用对数估算。取对数log10(F(n)) ≈ n * log10(φ) - log10(√5)log10(φ) 约等于 0.208987log10(√5) 约等于 0.349485。代入 n50005000 * 0.208987 - 0.349485 ≈ 1044.935 - 0.349485 ≈ 1044.585结果向上取整F(5000) 大约有 1045 位数字。一个 1045 位的十进制数远远超过long long的 19 位有效范围也超过__int128的 38 位。所以这道题不用高精度根本不可能 AC。看到这里你可能会想那 C 有没有内置的大整数类型很遗憾没有。标准库里的std::string虽然可以存数字但不会帮你做加法。所以只能自己造轮子把每一位数字存进数组然后模拟竖式加法。3.2 手写高精度加法的核心思路高精度加法的本质就是把我们小学学过的竖式加法搬到程序里。因为数字太大不能直接放进一个整数变量所以把每一位拆开。我用vectorint来存数字每一位存一个 0 到 9 的整数。这里有个非常重要的习惯倒着存。也就是说数组下标 0 存个位下标 1 存十位依此类推。为什么因为加法运算是从低位往高位进行的进位也从低位传递到高位。如果倒着存个位在a[0]十位在a[1]那么循环的时候从下标 0 开始自然就是低位到高位非常顺手。更关键的是当最高位出现进位时比如 999 1 1000我们只需要在数组末尾push_back(1)就完成了最高位扩展如果正着存最高位在数组前面插入新数字需要把整个数组往右移动效率低还容易出错。单次加法的伪代码逻辑carry 0 result [] len max(a.size(), b.size()) for i in 0..len-1: sum carry if i a.size(): sum a[i] if i b.size(): sum b[i] result.push_back(sum % 10) carry sum / 10 if carry ! 0: result.push_back(carry) return result每次把两个对应位置的数字以及上一次的进位相加和的个位留在当前位十位以上成为新的进位。最后如果还有进位要记得在最高位补上。3.3 高精度加法代码实现C我先把最核心的加法函数写出来。这段代码可以直接当作模板复用。#include bits/stdc.h using namespace std; // 高精度加法a ba、b 都是倒序存储的大整数 vectorint add(const vectorint a, const vectorint b) { vectorint c; int carry 0; int len max(a.size(), b.size()); for (int i 0; i len; i) { int sum carry; if (i a.size()) sum a[i]; if (i b.size()) sum b[i]; c.push_back(sum % 10); carry sum / 10; } if (carry) c.push_back(carry); return c; }这个函数有几个细节值得注意。第一len取两个数组中较长的那个长度。因为加法只能加到较长数字的最高位多出来的部分自然就是较短数字没有的位。循环里必须加上i a.size()和i b.size()这样的判断否则下标会越界程序直接崩溃。这个判断我以前经常漏尤其是两个数长度不一样的时候。第二carry最后一定要检查。如果最高位相加之后又产生了进位比如 999 1结果应该是 1000低位计算完后carry 1必须把这个 1 追加到数组末尾。漏掉这一步答案会少一位。第三函数参数我用const vectorint而不是传值。这是为了避免复制整个数组尤其当数字有 1000 多位时反复复制会拖慢速度。传引用对性能更友好加const是提醒自己不要误改原数据。3.4 Python 解法大整数是天然福利如果你用 Python这道题可以说简单得有点“欺负人”。因为 Python 的整数天生支持任意精度不需要手写高精度直接用普通变量算斐波那契就行。n int(input()) if n 1: print(1) elif n 2: print(2) else: a, b 1, 2 for _ in range(3, n 1): a, b b, a b print(b)代码很短核心就是滚动更新两个变量。a和b分别保存f[i-2]和f[i-1]每轮循环把f[i-1]赋给a把f[i-1] f[i-2]赋给b。虽然 Python 的整数运算在底层也是大整数运算速度不一定比 C 手写高精度快但写起来简洁适合快速验证算法思路。如果你还在学 C我建议还是把高精度加法老老实实写一遍。因为这是竞赛和面试里非常基础的工具后面很多大数题目都用得上。Python 简单是简单但会掩盖底层实现细节。4. 完整AC代码与本地测试4.1 最终提交的C版本我把完整代码整理出来。这里用了一个小技巧用三个变量滚动保存结果而不是开一个二维数组f[5001][]这样能节省不少内存。因为递推式f[i] f[i-1] f[i-2]只依赖前两个状态中间的状态用完就可以丢。#include bits/stdc.h using namespace std; vectorint add(const vectorint a, const vectorint b) { vectorint c; int carry 0; int len max(a.size(), b.size()); for (int i 0; i len; i) { int sum carry; if (i a.size()) sum a[i]; if (i b.size()) sum b[i]; c.push_back(sum % 10); carry sum / 10; } if (carry) c.push_back(carry); return c; } int main() { int n; cin n; if (n 1) { cout 1 endl; return 0; } if (n 2) { cout 2 endl; return 0; } vectorint f0(1, 1); // f[1] 1 vectorint f1(1, 2); // f[2] 2 vectorint f2; for (int i 3; i n; i) { f2 add(f0, f1); f0 f1; f1 f2; } for (int i f1.size() - 1; i 0; i--) { cout f1[i]; } cout endl; return 0; }输出时因为数组是倒序存的所以要从最后一个下标往前遍历打印。如果你按正序打印会得到完全颠倒的数字。这个小细节我当年第一次写的时候就犯过输出结果缺胳膊少腿查了半天才发现。4.2 本地怎么自测几个必须验的值提交之前最好先在本地验证几个小数据因为数据范围大之后错误不容易肉眼发现。我先验这几个n 1输出1n 2输出2n 3输出3n 4输出5n 10输出89n 20输出10946这些值都是斐波那契数列可以直接手算或者用 Python 的小脚本验证。如果这些边界值都对了说明递推式和高精度加法大概率没有问题。还有一个我自己觉得挺有用的验证方法用 Python 写一个同样逻辑的脚本生成n 5000的结果再把 C 程序跑出来的结果跟它对拍。两边结果一致那基本就稳了。这个方法不仅适用于这题所有高精度题目都可以这么干Python 相当于你的“参考实现”。4.3 踩坑记录这些错误我都犯过这里整理几个我在做这道题以及类似高精度递推题时真实踩过的坑。典型错误发生原因解决办法忘记特判 n1 或 n2循环从 3 开始n 小时 f0/f1 未正确初始化单独处理 n2 的情况数组正序存储从高位开始打印没有意识到进位在末尾统一倒序存储输出时逆序打印漏掉最后 carry高位相加产生进位时结果少一位算完循环后检查 carry 是否为 1循环内没有判断下标是否越界两个数长度不同时短的数组访问越界每次访问前判断i size()vector传值复制频繁复制大数组导致超时参数改成const vectorint输出顺序错误倒序存储却正序输出从size()-1循环到 0还有一个心态上的坑不要以为样例过了就一定能 AC。洛谷这类题库的样例通常比较小只覆盖最基础的情况真正卡人的是边界和大数据。所以提交之前一定要自己构造几个边界值测一测。比如n 1、n 2、n 5000这三个值至少得保证第一个和第二个不会崩溃第三个不会超时。5. 从 P1255 延伸出去爬楼梯问题还能怎么考5.1 变式一每次可以走 1、2、3 级如果题目改成每次可以走 1 级、2 级或者 3 级那么递推式会变成f[i] f[i-1] f[i-2] f[i-3]因为要到达第 i 级最后一步可能从 i-1、i-2、i-3 这三个位置过来。边界条件也要相应调整f[1] 1f[2] 2f[3] 4然后从i 4开始循环。你会发现核心思路完全一样改变的只是状态转移方程里的项数。这类变式在洛谷和各类OJ上很常见。它考察的其实是同一个能力能不能把“最后一步的所有可能”枚举完整并且正确写出递推关系。5.2 变式二加了限制条件的爬楼梯还有一类题会引入限制条件比如“不能连续走两级台阶”或者“某些编号的台阶坏掉了不能踩”。这种题看起来复杂但解决套路依然不变定义状态时可能要额外加一维来记录上一步走了几级。比如f[i][0] 表示走到第 i 级且最后一步走了 1 级 f[i][1] 表示走到第 i 级且最后一步走了 2 级这样就能在状态转移里限制“如果上一步走了 2 级这一步就不能再走 2 级”。这种“加维度”的技巧在动态规划里非常经典从一道简单的爬楼梯题可以一路延伸出很多变形。理解了 P1255 的基础递推后面遇到这些复杂变式会更容易上手。5.3 高精度模板沉淀一次封装到处复用做这道题最有价值的收获之一是得到一个可靠的高精度加法模板。我建议你把add函数单独保存下来以后遇到任何需要大数相加的题目直接复制过来用就行。甚至可以把vectorint封装成一个结构体重载运算符让代码更接近普通整数写法。struct BigInt { vectorint digit; // 倒序存储 BigInt(int x 0) { if (x 0) digit.push_back(0); while (x 0) { digit.push_back(x % 10); x / 10; } } BigInt operator(const BigInt other) const { BigInt result; result.digit.clear(); int carry 0; int len max(digit.size(), other.digit.size()); for (int i 0; i len; i) { int sum carry; if (i digit.size()) sum digit[i]; if (i other.digit.size()) sum other.digit[i]; result.digit.push_back(sum % 10); carry sum / 10; } if (carry) result.digit.push_back(carry); return result; } };封装好之后递推代码就变成了BigInt f0(1), f1(2), f2; f2 f0 f1;代码的可读性会高很多。当然对于这道题不封装也完全能过。但是如果你后面打算打竞赛或者刷更多算法题这类基础模板越早沉淀越好。做这道题让我最有感触的是一道看似“秒杀”的斐波那契题真正上手才会发现里面藏着这么多细节。从递推式的推导到结果位数的估算再到高精度手写实现每一步都在考察基本功。如果你也是刷题路上的一员我建议不要急着看题解先自己把n50的结果算出来体会一下数字增长的速度再动手实现高精度整个过程会顺畅很多。