• 示例工程

导读

本文基于 doocs/leetcode 开源仓库中 0070.Climbing Stairs 题解文档 展开，系统讲解 LeetCode 第 70 题"爬楼梯"的完整解题链路：从建立递推关系、滚动变量优化空间，到矩阵快速幂将时间复杂度从 O(n) 压到 O(log n)。读完本文，你将掌握斐波那契型递推问题的通用分析范式，以及线性递推如何借助矩阵乘法实现指数级加速，并能直接套用仓库内 Python、Java、C++、Go、TypeScript、Rust、JavaScript、PHP 八种语言的现成实现。

一、题目描述与问题建模

假设你正在爬楼梯。需要n阶你才能到达楼顶。每次你可以爬1或2个台阶。你有多少种不同的方法可以爬到楼顶呢？

示例 1：输入：n = 2，输出：2解释：两种方法——1 阶 + 1 阶、2 阶。

示例 2：输入：n = 3，输出：3解释：三种方法——1 阶 + 1 阶 + 1 阶、1 阶 + 2 阶、2 阶 + 1 阶。

提示：1 <= n <= 45

问题建模的关键洞察在于最后一步决策的唯一性：到达第n阶，最后一步要么是从第n-1阶爬 1 阶上来，要么是从第n-2阶爬 2 阶上来。这两条路径互斥且覆盖全部情况，因此方案数满足：

$$ f[i] = f[i - 1] + f[i - 2] $$

这正是斐波那契数列的递推形式，区别仅在于初始条件与下标定义。若直接按此关系递归求解，n <= 45时同一子问题会被反复展开，指数级的时间开销完全不可接受（这也是原文档中明确指出"直接按此递归时间无法接受"的原因）；自底向上递推即可彻底避免重复计算。

二、方法一：递推（滚动变量优化）

1. 状态定义与转移方程

定义f[i]表示爬到第i阶楼梯的方法数，由上式可得转移方程f[i] = f[i - 1] + f[i - 2]。

初始条件为：

• f[0] = 1：爬到第 0 阶（即起点）的方法数为 1；
• f[1] = 1：爬到第 1 阶的方法数为 1。

答案即为f[n]。

2. 空间优化：从数组到两个变量

观察转移方程可以发现，f[i]只与f[i - 1]和f[i - 2]有关，更早的状态不会再被使用。因此无需保留整个f数组，只需要两个变量a和b滚动维护"前两项"即可，空间复杂度由 O(n) 降至O(1)。

整体复杂度：时间复杂度 O(n)，空间复杂度 O(1)。

3. 仓库源码级实现对照

仓库中 [Solution.py](https://link.gitcode.com/i/5bc73dddfe213801f6f4065215caf13e/blob/719172c2745794a3fd496df6dc07588f7ccd98d6/lcp/LCP 05. 发 LeetCoin/Solution.py?utm_source=gitcode_repo_files)、[Solution.java](https://link.gitcode.com/i/5bc73dddfe213801f6f4065215caf13e/blob/719172c2745794a3fd496df6dc07588f7ccd98d6/lcp/LCP 05. 发 LeetCoin/Solution.java?utm_source=gitcode_repo_files) 等文件正是这一思路的直接落地，代码与题解文档中的示例完全一致，可直接复制运行：

Python3（见 [Solution.py](https://link.gitcode.com/i/5bc73dddfe213801f6f4065215caf13e/blob/719172c2745794a3fd496df6dc07588f7ccd98d6/lcp/LCP 05. 发 LeetCoin/Solution.py?utm_source=gitcode_repo_files)）：

class Solution: def climbStairs(self, n: int) -> int: a, b = 0, 1 for _ in range(n): a, b = b, a + b return b

这里a, b = 0, 1对应f[0]、f[1]的前置初值，循环n次后b恰好等于f[n]。由于n >= 1，循环至少执行一次，b不会停留在初值，结果正确。

Java（见 [Solution.java](https://link.gitcode.com/i/5bc73dddfe213801f6f4065215caf13e/blob/719172c2745794a3fd496df6dc07588f7ccd98d6/lcp/LCP 05. 发 LeetCoin/Solution.java?utm_source=gitcode_repo_files)）：

class Solution { public int climbStairs(int n) { int a = 0, b = 1; for (int i = 0; i < n; ++i) { int c = a + b; a = b; b = c; } return b; } }

C++：

class Solution { public: int climbStairs(int n) { int a = 0, b = 1; for (int i = 0; i < n; ++i) { int c = a + b; a = b; b = c; } return b; } };

Go：

func climbStairs(n int) int { a, b := 0, 1 for i := 0; i < n; i++ { a, b = b, a+b } return b }

TypeScript：

function climbStairs(n: number): number { let p = 1; let q = 1; for (let i = 1; i < n; i++) { [p, q] = [q, p + q]; } return q; }

TypeScript 版本采用了不同的初值设定（p = q = 1，即f[1] = f[2] = 1的等价变形），循环从i = 1到n - 1，同样得到f[n]，可见初值定义方式可以灵活调整，只要保持递推关系一致即可。

Rust：

impl Solution { pub fn climb_stairs(n: i32) -> i32 { let (mut p, mut q) = (1, 1); for i in 1..n { let t = p + q; p = q; q = t; } q } }

JavaScript：

/** * @param {number} n * @return {number} */ var climbStairs = function (n) { let a = 0, b = 1; for (let i = 0; i < n; ++i) { const c = a + b; a = b; b = c; } return b; };

PHP（该语言版本使用显式 DP 数组，便于对照理解转移过程）：

class Solution { /** * @param Integer $n * @return Integer */ function climbStairs($n) { if ($n <= 2) { return $n; } $dp = [0, 1, 2]; for ($i = 3; $i <= $n; $i++) { $dp[$i] = $dp[$i - 2] + $dp[$i - 1]; } return $dp[$n]; } }

仓库中对应可运行文件还包括 [Solution.cpp](https://link.gitcode.com/i/5bc73dddfe213801f6f4065215caf13e/blob/719172c2745794a3fd496df6dc07588f7ccd98d6/lcp/LCP 05. 发 LeetCoin/Solution.cpp?utm_source=gitcode_repo_files)、[Solution.go](https://link.gitcode.com/i/5bc73dddfe213801f6f4065215caf13e/blob/719172c2745794a3fd496df6dc07588f7ccd98d6/lcp/LCP 29. 乐团站位/Solution.go?utm_source=gitcode_repo_files)、[Solution.js](https://link.gitcode.com/i/5bc73dddfe213801f6f4065215caf13e/blob/719172c2745794a3fd496df6dc07588f7ccd98d6/lcp/LCP 01. 猜数字/Solution.js?utm_source=gitcode_repo_files)、[Solution.rs](https://link.gitcode.com/i/5bc73dddfe213801f6f4065215caf13e/blob/719172c2745794a3fd496df6dc07588f7ccd98d6/lcp/LCP 06. 拿硬币/Solution.rs?utm_source=gitcode_repo_files)、[Solution.ts](https://link.gitcode.com/i/5bc73dddfe213801f6f4065215caf13e/blob/719172c2745794a3fd496df6dc07588f7ccd98d6/lcp/LCP 29. 乐团站位/Solution.ts?utm_source=gitcode_repo_files)、[Solution.php](https://link.gitcode.com/i/5bc73dddfe213801f6f4065215caf13e/blob/719172c2745794a3fd496df6dc07588f7ccd98d6/lcp/LCP 06. 拿硬币/Solution.php?utm_source=gitcode_repo_files)，读者可逐一对照阅读。

4. 递推解法的适用范围

O(n) 递推对本题n <= 45已经绰绰有余（答案最大约 18 亿量级，仍落在 32 位整数范围内）。但从源码结构看，仓库特意为本题准备了第二套解法（Solution2.*系列文件），正是为了演示当n进一步扩大时，线性递推如何升级为对数级算法，这引出下面的方法二。

三、方法二：矩阵快速幂加速递推

1. 为什么需要矩阵快速幂

线性齐次递推F_n = F_{n-1} + F_{n-2}可以被写成矩阵乘法的形式：每一步转移相当于乘上一个固定的 2×2 转移矩阵。连续转移n次即等价于矩阵的n次幂，而矩阵幂可以借助"快速幂"思想（二进制分解指数）在 O(log n) 次矩阵乘法内完成。常数略大，但适合需要大规模加速同一递推的场景。

2. 转移矩阵的推导

设Fib(n)表示 1×2 矩阵[F_n F_{n-1}]，其中F_n、F_{n-1}分别是第n个、第n-1个斐波那契数。我们希望由Fib(n-1) = [F_{n-1} F_{n-2}]推出Fib(n)，即寻找矩阵base使得：

$$ \begin{bmatrix} F_{n - 1} & F_{n - 2} \end{bmatrix} \times base = \begin{bmatrix} F_n & F_{n - 1} \end{bmatrix} $$

由F_n = F_{n-1} + F_{n-2}可知，base的第一列应为[1, 1]^T（用于生成F_n），第二列应为[1, 0]^T（用于生成F_{n-1}），于是：

$$ \begin{bmatrix} F_{n - 1} & F_{n - 2} \end{bmatrix} \times \begin{bmatrix}1 & 1 \ 1 & 0\end{bmatrix} = \begin{bmatrix} F_n & F_{n - 1} \end{bmatrix} $$

定义初始矩阵res = [1 1]（即F_1 = 1, F_0 = 1），那么F_n等于res乘以base^(n-1)所得结果矩阵第一行的第一个元素，即：

$$ F_n = \left( \begin{bmatrix} 1 & 1 \end{bmatrix} \times \begin{bmatrix}1 & 1 \ 1 & 0\end{bmatrix}^{n-1} \right)[0][0] $$

使用矩阵快速幂求解即可。整体复杂度：时间复杂度 O(log n)，空间复杂度 O(1)。

3. 仓库源码级实现对照

仓库中的 [Solution2.py](https://link.gitcode.com/i/5bc73dddfe213801f6f4065215caf13e/blob/719172c2745794a3fd496df6dc07588f7ccd98d6/lcp/LCP 24. 数字游戏/Solution2.py?utm_source=gitcode_repo_files)、[Solution2.java](https://link.gitcode.com/i/5bc73dddfe213801f6f4065215caf13e/blob/719172c2745794a3fd496df6dc07588f7ccd98d6/lcp/LCP 24. 数字游戏/Solution2.java?utm_source=gitcode_repo_files) 等Solution2.*文件即为矩阵快速幂实现，与文档代码一致：

Python3（见 [Solution2.py](https://link.gitcode.com/i/5bc73dddfe213801f6f4065215caf13e/blob/719172c2745794a3fd496df6dc07588f7ccd98d6/lcp/LCP 24. 数字游戏/Solution2.py?utm_source=gitcode_repo_files)，借助 numpy 矩阵运算）：

import numpy as np class Solution: def climbStairs(self, n: int) -> int: res = np.asmatrix([(1, 1)], np.dtype("O")) factor = np.asmatrix([(1, 1), (1, 0)], np.dtype("O")) n -= 1 while n: if n & 1: res *= factor factor *= factor n >>= 1 return res[0, 0]

注意两点实现细节：np.dtype("O")使用 object 类型避免整数溢出风险；n -= 1对应上文推导中base的指数为n-1。循环内部是标准的快速幂模板——n & 1判断当前二进制位是否为 1，命中则累乘factor，随后factor自乘并右移指数。

Java（见 [Solution2.java](https://link.gitcode.com/i/5bc73dddfe213801f6f4065215caf13e/blob/719172c2745794a3fd496df6dc07588f7ccd98d6/lcp/LCP 24. 数字游戏/Solution2.java?utm_source=gitcode_repo_files)）：

class Solution { private final int[][] a = {{1, 1}, {1, 0}}; public int climbStairs(int n) { return pow(a, n - 1)[0][0]; } private int[][] mul(int[][] a, int[][] b) { int m = a.length, n = b[0].length; int[][] c = new int[m][n]; for (int i = 0; i < m; ++i) { for (int j = 0; j < n; ++j) { for (int k = 0; k < a[0].length; ++k) { c[i][j] += a[i][k] * b[k][j]; } } } return c; } private int[][] pow(int[][] a, int n) { int[][] res = {{1, 1}, {0, 0}}; while (n > 0) { if ((n & 1) == 1) { res = mul(res, a); } n >>= 1; a = mul(a, a); } return res; } }

这里mul实现的是标准的三层循环矩阵乘法，pow则是对指数做二进制分解：每次将a自乘（对应"平方"），当当前位为 1 时将a乘入res（对应"乘入结果"），最终res即为a^n。初始res = {{1, 1}, {0, 0}}与文档推导中的初始矩阵[1 1]对应。

C++（使用long long避免乘法中间结果溢出）：

class Solution { public: int climbStairs(int n) { vector<vector<long long>> a = {{1, 1}, {1, 0}}; return pow(a, n - 1)[0][0]; } private: vector<vector<long long>> mul(vector<vector<long long>>& a, vector<vector<long long>>& b) { int m = a.size(), n = b[0].size(); vector<vector<long long>> res(m, vector<long long>(n)); for (int i = 0; i < m; ++i) { for (int j = 0; j < n; ++j) { for (int k = 0; k < a[0].size(); ++k) { res[i][j] += a[i][k] * b[k][j]; } } } return res; } vector<vector<long long>> pow(vector<vector<long long>>& a, int n) { vector<vector<long long>> res = {{1, 1}, {0, 0}}; while (n) { if (n & 1) { res = mul(res, a); } a = mul(a, a); n >>= 1; } return res; } };

Go（使用自定义matrix类型）：

type matrix [2][2]int func climbStairs(n int) int { a := matrix{{1, 1}, {1, 0}} return pow(a, n-1)[0][0] } func mul(a, b matrix) (c matrix) { m, n := len(a), len(b[0]) for i := 0; i < m; i++ { for j := 0; j < n; j++ { for k := 0; k < len(a[0]); k++ { c[i][j] += a[i][k] * b[k][j] } } } return } func pow(a matrix, n int) matrix { res := matrix{{1, 1}, {0, 0}} for n > 0 { if n&1 == 1 { res = mul(res, a) } a = mul(a, a) n >>= 1 } return res }

TypeScript：

function climbStairs(n: number): number { const a = [ [1, 1], [1, 0], ]; return pow(a, n - 1)[0][0]; } function mul(a: number[][], b: number[][]): number[][] { const [m, n] = [a.length, b[0].length]; const c = Array(m) .fill(0) .map(() => Array(n).fill(0)); for (let i = 0; i < m; ++i) { for (let j = 0; j < n; ++j) { for (let k = 0; k < a[0].length; ++k) { c[i][j] += a[i][k] * b[k][j]; } } } return c; } function pow(a: number[][], n: number): number[][] { let res = [ [1, 1], [0, 0], ]; while (n) { if (n & 1) { res = mul(res, a); } a = mul(a, a); n >>= 1; } return res; }

JavaScript：

/** * @param {number} n * @return {number} */ var climbStairs = function (n) { const a = [ [1, 1], [1, 0], ]; return pow(a, n - 1)[0][0]; }; function mul(a, b) { const [m, n] = [a.length, b[0].length]; const c = Array(m) .fill(0) .map(() => Array(n).fill(0)); for (let i = 0; i < m; ++i) { for (let j = 0; j < n; ++j) { for (let k = 0; k < a[0].length; ++k) { c[i][j] += a[i][k] * b[k][j]; } } } return c; } function pow(a, n) { let res = [ [1, 1], [0, 0], ]; while (n) { if (n & 1) { res = mul(res, a); } a = mul(a, a); n >>= 1; } return res; }

仓库对应可运行文件为 [Solution2.cpp](https://link.gitcode.com/i/5bc73dddfe213801f6f4065215caf13e/blob/719172c2745794a3fd496df6dc07588f7ccd98d6/lcp/LCP 24. 数字游戏/Solution2.cpp?utm_source=gitcode_repo_files)、[Solution2.go](https://link.gitcode.com/i/5bc73dddfe213801f6f4065215caf13e/blob/719172c2745794a3fd496df6dc07588f7ccd98d6/lcp/LCP 24. 数字游戏/Solution2.go?utm_source=gitcode_repo_files)、[Solution2.js](https://link.gitcode.com/i/5bc73dddfe213801f6f4065215caf13e/blob/719172c2745794a3fd496df6dc07588f7ccd98d6/lcof/面试题33. 二叉搜索树的后序遍历序列/Solution2.js?utm_source=gitcode_repo_files)、[Solution2.ts](https://link.gitcode.com/i/5bc73dddfe213801f6f4065215caf13e/blob/719172c2745794a3fd496df6dc07588f7ccd98d6/lcp/LCP 24. 数字游戏/Solution2.ts?utm_source=gitcode_repo_files)。

4. 两种解法的对比与选型

在仓库中，两种实现以Solution.*与Solution2.*两套文件并列存放（见 0070.Climbing Stairs 目录），便于学习者直接对比同一思路在不同语言下的写法差异。

四、从本题延伸：斐波那契型递推的通用范式

爬楼梯问题本质上是"斐波那契型"递推的经典包装。同类问题在仓库中大量出现，理解本题等于掌握了一类问题的解法模板：

1. 识别递推关系：分析"最后一步"的可能动作，建立f[i] = f[i-1] + f[i-2]或类似形式的线性递推；
2. 确定初始条件：给出f[0]、f[1]（或f[1]、f[2]）的取值，注意不同定义方式下答案下标一致；
3. 滚动优化空间：只要转移只依赖固定数量的前序状态，即可用常量个变量替代整个 DP 数组；
4. 按需升级算法：当n大到线性时间不可接受时，将线性递推改写成矩阵形式并用快速幂加速到 O(log n)。

这一"识别递推 → 滚动优化 → 矩阵加速"的三步走思路，可以平移到几乎所有一维线性递推（如爬楼梯、斐波那契、跳台阶等）问题中，是面试与竞赛中复用率极高的算法范式。

参考资料

• 本题题解文档：README.md（含完整的中文推导过程）
• 英文版题解：README_EN.md
• 方法一（递推）源码：Solution.py / Solution.java / Solution.cpp / Solution.go / Solution.js / Solution.rs / Solution.ts / Solution.php
• 方法二（矩阵快速幂）源码：Solution2.py / Solution2.java / Solution2.cpp / Solution2.go / Solution2.js / Solution2.ts

• 示例工程