思路一：记忆化dfs
class Solution {
public:
unordered_map ump;
int dfs(int n) {
if (n == 1) return 1;
if (n == 2) return 2;
if (ump.count(n)) return ump[n];
ump[n] = dfs(n - 2) + dfs(n - 1);
return ump[n];
}
int climbStairs(int n) {
return dfs(n);
}
};
思路二：dp ---------->O(n)
具体：dp[i]表示到达i阶需要的步数 dp[i] = dp[i-1]+dp[i-2]
class Solution {
public:
int climbStairs(int n) {
if (n == 1) return 1;
if (n == 2) return 2;
int a = 1, b = 2, tmp;
for (int i = 3; i <= n; ++i) {
tmp = a;
a = b;
b = tmp + b;
}
return b;
}
};
思路三：时间优化，矩阵快速幂 O(logn)
class Solution {
public:
//矩阵快速幂，结果为求[1 1][1 0]的n次幂左上角的元素
vector> multiply(vector>matrix1, vector>matrix2) {
vector> ans(2, vector(2));
for (int i = 0; i < 2; ++i) {
for (int j = 0; j < 2; ++j)
ans[i][j] = matrix1[i][0] * matrix2[0][j] + matrix1[i][1] * matrix2[1][j];
}
return ans;
}
vector> matrixpow(vector>& matrix, int n) {
vector> ans = {{1, 0}, {0, 1}}; //
while (n) {
if (n & 1) {
ans = multiply(ans, matrix);
}
matrix = multiply(matrix, matrix);
n >>= 1;
}
return ans;
}
int climbStairs(int n) {
vector> matrix = {{1, 1}, {1, 0}};
auto result = matrixpow(matrix, n); //
return result[0][0];
}
};
易错点
1：搞一个单位矩阵，才能与矩阵相乘！！！
2：结果可能没超int， 但是相乘就会越界，所以临时矩阵都要声明为long long类型！！！
