京公网安备11010502063487号爬 n 阶楼梯到楼顶，每次可以爬 1 或 2 阶，问有多少种不同的方法。到第 n 阶的最后一步，要么是从第 n - 1 阶爬 1 阶，要么是从第 n - 2 阶爬 2 阶，所以方法数 f(n) = f(n-1) + f(n-2)，这就是斐波那契数列（f(0) = f(1) = 1）。这是最经典的动态规划入门题。本文用真实数据展示不带记忆化的递归调用次数如何爆炸，验证一个常见的"用黄金分割公式直接算"的想法在 n 多大时开始出错，用 Java 展示 32 位整数在 n = 46 时溢出，给出五种语言的实现，并把填表做成分步演示。
完整题目见官方页面（链接在文末）。题目限制 n 不超过 45（f(45) = 1836311903，刚好在 32 位整数范围内）。基准解是带记忆化的递归，直接按定义计算，与滚动变量的迭代是两种不同的写法。一共 11 组用例，n 取 1 到 6、10、20、30、44、45：
输入 [1] 输出 1 输入 [2] 输出 2 输入 [3] 输出 3 输入 [4] 输出 5 输入 [5] 输出 8 输入 [6] 输出 13
最直接的写法是 f(n) = f(n-1) + f(n-2) 直接递归，不记忆。同一个子问题会被重复计算很多次。下面是真实统计的调用次数和耗时：
不带记忆化的递归：调用次数与耗时 n=10: 结果 89，调用 177 次， 0.01 ms n=20: 结果 10946，调用 21891 次， 1.26 ms n=25: 结果 121393，调用 242785 次， 13.90 ms n=30: 结果 1346269，调用 2692537 次， 182.93 ms n=33: 结果 5702887，调用 11405773 次， 660.44 ms
调用次数几乎正好是结果的 2 倍减 1（n = 10 时 177 = 2 × 89 - 1，n = 33 时 11405773 = 2 × 5702887 - 1）。n 每增加 5，调用次数约乘 11（黄金分割数的 5 次方），耗时也一样：n = 30 时 183ms，n = 33 时 660ms。而迭代只需要 n 次加法。
斐波那契数列有封闭形式（Binet 公式），看起来可以直接一步算出：round(φ^(n+1) / √5)，其中 φ 是黄金分割数。但双精度浮点数只有约 15 到 16 位有效数字，n 变大后就会出误差。下面是真实计算的结果：
用通项公式（黄金分割数的幂，双精度浮点）round(phi^(n+1) / sqrt(5)) 计算，n 从 1 起第一个与整数递推结果不同的 n = 70：公式得到 308061521170130，正确值 308061521170129
用通项公式，从 n = 1 起第一个与整数递推结果不一致的是 n = 70：公式得到 308061521170130，正确值是 308061521170129，相差 1。这道题的 n 不超过 45，公式在题目范围内碰巧一直是对的，但它不能推广到更大的 n；而整数递推没有这个问题（Python 的整数不受限制，其他语言里用 64 位整数可以精确到 n = 90 左右，这个上限我没有实测）。
f(46) = 2971215073，超过了 32 位有符号整数的最大值 2147483647。题目把 n 限制在 45，正是为了避免这个问题。下面是真实运行的 Java 程序，对比 int 和 long：
方法数增长到 n = 46 时超过了 32 位整数的最大值 2147483647（题目限制 n 不超过 45）： Java int: n=45 -> 1836311903 Java int: n=46 -> -1323752223 Java int: n=47 -> 512559680 Java long: n=45 -> 1836311903 Java long: n=46 -> 2971215073 Java long: n=47 -> 4807526976
int 在 n = 46 时得到 -1323752223，n = 47 时得到 512559680，都是溢出回绕的结果；long 得到正确的 2971215073 和 4807526976。n = 45 时两者一致。
只需要前两项，不用整个数组：a 是爬到第 i-1 阶的方法数，b 是爬到第 i 阶的方法数，初始都是 1。每一步：(a, b) = (b, a + b)。循环 n - 1 次之后，b 就是爬到第 n 阶的方法数。时间 O(n)，空间 O(1)。Python、Java、Go、JavaScript、C++ 都是真实编译运行的。
Python · 解法代码def solve(n): a, b = 1, 1 # a = 爬到第 i-1 阶的方法数，b = 爬到第 i 阶的方法数（第 0 阶、第 1 阶各有 1 种） for _ in range(n - 1): a, b = b, a + b # 到第 i+1 阶：从第 i 阶爬 1 步，或从第 i-1 阶爬 2 步 return b
$ python3 solution.py # 统一入口：逐行读取 cases.jsonl，调用上面的 solve，打印 JSON [1] → 1 [2] → 2 [3] → 3 [4] → 5 [5] → 8 [6] → 13
Java · 解法代码class Solution { public int climbStairs(int n) { int a = 1, b = 1; // a = 爬到第 i-1 阶的方法数，b = 爬到第 i 阶的方法数 for (int i = 2; i <= n; i++) { int c = a + b; // 到第 i 阶：从第 i-1 阶爬 1 步，或从第 i-2 阶爬 2 步 a = b; b = c; } return b; } }
$ javac -d build Main.java Solution.java && java -cp build Main < cases.jsonl [1] → 1 [2] → 2 [3] → 3 [4] → 5 [5] → 8 [6] → 13
Go · 解法代码func climbStairs(n int) int { a, b := 1, 1 // a = 爬到第 i-1 阶的方法数，b = 爬到第 i 阶的方法数 for i := 2; i <= n; i++ { a, b = b, a+b // 到第 i 阶：从第 i-1 阶爬 1 步，或从第 i-2 阶爬 2 步 } return b }
$ go build -o bin . && ./bin < cases.jsonl [1] → 1 [2] → 2 [3] → 3 [4] → 5 [5] → 8 [6] → 13
JavaScript · 解法代码function climbStairs(n) { let a = 1, b = 1; // a = 爬到第 i-1 阶的方法数，b = 爬到第 i 阶的方法数 for (let i = 2; i <= n; i++) { [a, b] = [b, a + b]; // 到第 i 阶：从第 i-1 阶爬 1 步，或从第 i-2 阶爬 2 步 } return b; }
$ node run.js < cases.jsonl [1] → 1 [2] → 2 [3] → 3 [4] → 5 [5] → 8 [6] → 13
C++ · 解法代码using namespace std; class Solution { public: int climbStairs(int n) { int a = 1, b = 1; // a = 爬到第 i-1 阶的方法数，b = 爬到第 i 阶的方法数 for (int i = 2; i <= n; i++) { int c = a + b; // 到第 i 阶：从第 i-1 阶爬 1 步，或从第 i-2 阶爬 2 步 a = b; b = c; } return b; } };
$ clang++ -std=c++17 -O2 -o bin sol.cpp && ./bin < cases.jsonl [1] → 1 [2] → 2 [3] → 3 [4] → 5 [5] → 8 [6] → 13
共 11 组用例（含边界），以暴力解的结果为基准逐组比对： Python 通过 11/11 Java 通过 11/11 Go 通过 11/11 JavaScript 通过 11/11 C++ 通过 11/11
Python 版本另外和带记忆化的递归做了对拍，n 取 1 到 45 的随机值：
随机对拍 45 组（n 从 1 到 45 的随机值），solve 与 brute 的结果全部一致。
n 一共只有 45 种取值，上面的固定用例加随机对拍覆盖了其中大部分。另外四种语言只在上面 11 组固定用例上验证过，其中包含最大的 n = 44 和 n = 45。
下面的演示用 n = 7，填出 f(2) 到 f(7)：2、3、5、8、13、21。爬到第 7 阶有 21 种方法。每一帧都是把上面的解法在这组输入上真实执行记录下来的，运行器还检查了演示的最终结果与 solve 的返回值一致。