70. 爬楼梯
题目描述
一段楼梯共有 n 级台阶。每一步可以上 1 级，也可以上 2 级。
返回从地面走到第 n 级共有多少种不同的走法。两种走法只要某一步的步长序列不同，就算不同。
示例 1
输入：n = 2 输出：2
解释：两种走法：1+1，或者 2。
示例 2
输入：n = 3 输出：3
解释：三种走法：1+1+1、1+2、2+1。
数据范围
1 <= n <= 45
解题思路：动态规划（滚动变量）
到第 i 阶只能从 i-1 或 i-2 来，因此滚动保存两个前状态。
为什么正确
完成 k 次循环后，a=f(k)、b=f(k+1)；完成 n 次后返回 a。
复杂度分析
时间 O(n)，空间 O(1)。
易错点
初始值是 f(0)=1，表示空走法；错设为 0 会让整个序列偏移。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def climbStairs(self, n: int) -> int:
a, b = 1, 1
for _ in range(n):
a, b = b, a + b
return aclass Solution {
public int climbStairs(int n) {
long a = 1, b = 1;
for (int i = 0; i < n; i++) {
long c = a + b;
a = b; b = c;
}
return (int) a;
}
}class Solution {
public:
int climbStairs(int n) {
long long a = 1, b = 1;
for (int i = 0; i < n; i++) {
long long c = a + b;
a = b; b = c;
}
return a;
}
};func climbStairs(n int) int {
a, b := 1, 1
for i := 0; i < n; i++ {
a, b = b, a+b
}
return a
}var climbStairs = function(n) {
let a = 1, b = 1;
for (let i = 0; i < n; i++) {
[a, b] = [b, a + b];
}
return a;
};function climbStairs(n: number): number {
let a = 1, b = 1;
for (let i = 0; i < n; i++) {
[a, b] = [b, a + b];
}
return a;
};其他解法
滚动变量 O(n) 最简单；矩阵快速幂 O(log n)，适合 n 极大或需要取模的线性递推题。
解法 2：矩阵快速幂 时间 O(log n)，空间 O(1)
递推 f(n)=f(n-1)+f(n-2) 可以写成矩阵形式：[f(n+1), f(n)] = [[1,1],[1,0]] × [f(n), f(n-1)]。因此 f(n) 等于矩阵 [[1,1],[1,0]] 的 n 次幂左上角的元素。用快速幂把 n 按二进制拆开，只做 O(log n) 次 2×2 矩阵乘法。
n 很大时明显更快，而且这个套路可以推广到任意线性递推。代码比滚动变量长，本题 n ≤ 45 时并没有实际收益。
class Solution:
def climbStairs(self, n: int) -> int:
def mul(a, b):
return [
[a[0][0] * b[0][0] + a[0][1] * b[1][0], a[0][0] * b[0][1] + a[0][1] * b[1][1]],
[a[1][0] * b[0][0] + a[1][1] * b[1][0], a[1][0] * b[0][1] + a[1][1] * b[1][1]],
]
res = [[1, 0], [0, 1]]
base = [[1, 1], [1, 0]]
while n > 0:
if n & 1:
res = mul(res, base)
base = mul(base, base)
n >>= 1
return res[0][0]class Solution {
long[][] mul(long[][] a, long[][] b) {
long[][] c = new long[2][2];
for (int i = 0; i < 2; i++)
for (int j = 0; j < 2; j++)
c[i][j] = a[i][0] * b[0][j] + a[i][1] * b[1][j];
return c;
}
public int climbStairs(int n) {
long[][] res = {{1, 0}, {0, 1}};
long[][] base = {{1, 1}, {1, 0}};
while (n > 0) {
if ((n & 1) == 1) res = mul(res, base);
base = mul(base, base);
n >>= 1;
}
return (int) res[0][0];
}
}class Solution {
public:
typedef vector<vector<long long>> Mat;
Mat mul(const Mat& a, const Mat& b) {
Mat c(2, vector<long long>(2, 0));
for (int i = 0; i < 2; i++)
for (int j = 0; j < 2; j++)
c[i][j] = a[i][0] * b[0][j] + a[i][1] * b[1][j];
return c;
}
int climbStairs(int n) {
Mat res = {{1, 0}, {0, 1}};
Mat base = {{1, 1}, {1, 0}};
while (n > 0) {
if (n & 1) res = mul(res, base);
base = mul(base, base);
n >>= 1;
}
return (int)res[0][0];
}
};func climbStairs(n int) int {
mul := func(a, b [2][2]int) [2][2]int {
var c [2][2]int
for i := 0; i < 2; i++ {
for j := 0; j < 2; j++ {
c[i][j] = a[i][0]*b[0][j] + a[i][1]*b[1][j]
}
}
return c
}
res := [2][2]int{{1, 0}, {0, 1}}
base := [2][2]int{{1, 1}, {1, 0}}
for n > 0 {
if n&1 == 1 {
res = mul(res, base)
}
base = mul(base, base)
n >>= 1
}
return res[0][0]
}var climbStairs = function(n) {
const mul = (a, b) => [
[a[0][0] * b[0][0] + a[0][1] * b[1][0], a[0][0] * b[0][1] + a[0][1] * b[1][1]],
[a[1][0] * b[0][0] + a[1][1] * b[1][0], a[1][0] * b[0][1] + a[1][1] * b[1][1]],
];
let res = [[1, 0], [0, 1]];
let base = [[1, 1], [1, 0]];
while (n > 0) {
if (n & 1) res = mul(res, base);
base = mul(base, base);
n >>= 1;
}
return res[0][0];
};function climbStairs(n: number): number {
const mul = (a: number[][], b: number[][]): number[][] => [
[a[0][0] * b[0][0] + a[0][1] * b[1][0], a[0][0] * b[0][1] + a[0][1] * b[1][1]],
[a[1][0] * b[0][0] + a[1][1] * b[1][0], a[1][0] * b[0][1] + a[1][1] * b[1][1]],
];
let res = [[1, 0], [0, 1]];
let base = [[1, 1], [1, 0]];
while (n > 0) {
if (n & 1) res = mul(res, base);
base = mul(base, base);
n >>= 1;
}
return res[0][0];
}