欢迎访问LeetCode题解合集
题目描述
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢?
注意: 给定 n 是一个正整数。
示例 1:
输入: 2
输出: 2
解释: 有两种方法可以爬到楼顶。
1. 1 阶 + 1 阶
2. 2 阶
示例 2:
输入: 3
输出: 3
解释: 有三种方法可以爬到楼顶。
1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶
题解:
法一:
动态规划。
设 f[i]
表示跳到第 i
阶楼梯的方案数,那么转移方程很容易想到:f[i] = f[i - 1] + f[i - 2]
,初始条件:f[0] = f[1] = 1
。
时间复杂度:$O(n)$
额外空间复杂度:$O(n)$
class Solution {
public:
int climbStairs(int n) {
vector<int>f(n + 1);
f[0] = f[1] = 1;
for ( int i = 2; i <= n; ++i )
f[i] = f[i - 1] + f[i - 2];
return f[n];
}
};
/*
时间:0ms,击败:100.00%
内存:5.9MB,击败:87.64%
*/
可以发现, f[i]
只跟 f[i - 1]
和 f[i - 2]
有关,那么可以使用滚动数组的思想,使用两个变量 a
和 b
分别表示 f[i - 1
] 和 f[i - 2]
,遍历过程中更新对应的值即可。
额外空间复杂度:$O(1)$
class Solution {
public:
int climbStairs(int n) {
int a = 1, b = 1, c;
for ( int i = 2; i <= n; ++i ) {
c = a + b;
a = b;
b = c;
}
return b;
}
};
/*
时间:0ms,击败:100.00%
内存:5.7MB,击败:99.46%
*/
法二:
方法一只适用于 n
比较小的情况,如果要求 $10^{18}$ 的结果,上面的方法肯定没法搞定,只能考虑 $O(logn)$ 或者 $O(1)$ 的解法。
虑斐波那契数列的递推公式:$F(n)=F(n-1)+F(n-2)$ ,这是一个二阶递推数列,于是我们可以用矩阵乘法的形式进行表示:
$$
\left[\begin{matrix} F(n) & F(n-1) \end{matrix} \right] =
\left[\begin{matrix}F(n-1) & F(n-2)\end{matrix}\right] \times
\left[\begin{matrix} 1 & 1\\1 & 0 \end{matrix}\right]
$$
观察可发现:
$$
\left[\begin{matrix} F(3) & F(2)\end{matrix}\right] =
\left[\begin{matrix}F(2) & F(1)\end{matrix}\right] \times
\left[\begin{matrix} 1 & 1\\1 & 0 \end{matrix}\right] =
\left[\begin{matrix} 2 & 1 \end{matrix}\right] \times
\left[\begin{matrix} 1 & 1\\1 & 0 \end{matrix}\right]
$$
$$ \left[\begin{matrix} F(4) & F(3) \end{matrix}\right] = \left[\begin{matrix}F(3) & F(2) \end{matrix}\right] \times \left[\begin{matrix} 1 & 1\\1 & 0 \end{matrix}\right] = \left[\begin{matrix} 2 & 1 \end{matrix}\right] \times \left[\begin{matrix} 1 & 1\\1 & 0 \end{matrix}\right]^2 $$
$$ … $$
$$ \left[\begin{matrix} F(n) & F(n-1) \end{matrix}\right] = \left[\begin{matrix} F(n-1) & F(n-2) \end{matrix}\right] \times \left[\begin{matrix} 1 & 1\\1 & 0 \end{matrix}\right] = \left[\begin{matrix} 2 & 1 \end{matrix}\right] \times \left[\begin{matrix} 1 & 1\\1 & 0 \end{matrix}\right]^{n-2} $$
于是题目就变成了如何快速的求一个矩阵的 n 次方问题,那我们可以使用 快速幂 分分钟搞定。
时间复杂度:$O(n)$
额外空间复杂度:$O(1)$
class Solution {
public:
using LL = long long;
void mat_mul( vector<vector<LL>>& ret, vector<vector<LL>>& ans ) {
vector<vector<LL>> tmp(2, vector<LL>(2, 0LL));
for ( int i = 0; i < 2; ++i ) {
for ( int j = 0; j < 2; ++j ) {
for ( int k = 0; k < 2; ++k ) {
tmp[i][j] += ret[i][k] * ans[k][j];
}
}
}
ret = tmp;
}
int climbStairs(int n) {
if ( n <= 3 ) return n;
vector<vector<LL>> ret = { {1, 0}, {0, 1} };
vector<vector<LL>> ans = { {1, 1}, {1, 0} };
n -= 2;
while ( n ) {
if ( n & 1 ) mat_mul( ret, ans );
mat_mul( ans, ans );
n >>= 1;
}
return 2 * ret[0][0] + ret[1][0];
}
};
/*
时间:0ms,击败:100.00%
内存:5.9MB,击败:86.85%
*/
还有一种数学解法,不太会。。。