Leecode 70. 爬楼梯 DP/矩阵快速幂

原题链接： 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;
    }
};

矩阵快速幂 这里可以参考一下官方解答：

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];
    }
};

通项公式 参考官方解答：

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);
    }
};