原题链接：Leecode 70. 爬楼梯
DP：
其实就是斐波拉契的变形，但是这里我们要搞清楚，为什么有f(x)=f(x?1)+f(x?2)的状态转移方程：因为我们可以通过在 n-1 阶的楼梯爬 1 步来达到 n 楼层，以及通过在 n - 2 阶 的楼梯爬 2 步来达到 n 楼层。所以就是这两种情况的总和。
class Solution {
public:
int climbStairs(int n) {
int a=1,b=1,c=1;
for(int i=2;i<=n;i++)
{
c=a+b;a=b;b=c;
}
return c;
}
};
矩阵快速幂
这里可以参考一下官方解答：Leecode 70. 爬楼梯 官解
class Solution {
public:
vector<vector<long long>> multiply(vector<vector<long long>>& a,vector<vector<long long>>& b)
{
vector<vector<long long>> res(2,vector<long long>(2));
for(int i=0;i<2;i++)
{
for(int j=0;j<2;j++)
{
for(int k=0;k<2;k++)
{
res[i][j]+=a[i][k]*b[k][j];
}
}
}
return res;
}
vector<vector<long long>> quickpow(vector<vector<long long>>& a,int k)
{
vector<vector<long long>> res(2,vector<long long>(2));
for(int i=0;i<2;i++) res[i][i]=1;
while(k)
{
if(k&1) res=multiply(res,a);
a=multiply(a,a);
k>>=1;
}
return res;
}
int climbStairs(int n) {
vector<vector<long long>> a={{1, 1}, {1, 0}};
vector<vector<long long>> res=quickpow(a,n);
return res[0][0];
}
};
通项公式
参考官方解答：Leecode 70. 爬楼梯 官解
class Solution {
public:
int climbStairs(int n) {
double n1=sqrt(5);
double res=(pow((1+n1)/2,n+1)+pow((1-n1)/2,n+1))/n1;
return (int)round(res);
}
};
