[数据结构与算法]LeetCode 70.爬楼梯

常规解法：动态规划

dp[n]表示楼梯阶数为n时有多少种上楼方案
状态转移方程dp[n]=dp[n-1]+dp[n-2]
边界条件：dp[1]=1 dp[2]=2

矩阵快速幂

利用矩阵推导出递推关系，即构造出一个矩阵的n次方乘一个列向量得到一个列向量，此时就可以通过矩阵的n次幂来得到目标列向量(该列向量包含所要求的f(n))

递推式子：
$$f(n)=f(n?1)+f(n?2)$$
利用矩阵构造递推关系:
$$\left[\begin{array}{cc}1& 1\\ 1& 0\end{array}\right]?\left[\begin{array}{c}f(n)\\ f(n?1)\end{array}\right]=\left[\begin{array}{c}f(n)?f(n?1)\\ f(n)\end{array}\right]$$
由于
$$\left[\begin{array}{c}f(n)?f(n?1)\\ f(n)\end{array}\right]=\left[\begin{array}{c}f(n+1)\\ f(n)\end{array}\right]$$
进而得出
$$\left[\begin{array}{cc}1& 1\\ 1& 0\end{array}\right]?\left[\begin{array}{c}f(n)\\ f(n?1)\end{array}\right]=\left[\begin{array}{c}f(n+1)\\ f(n)\end{array}\right]$$
最终的递推关系为：
$${\left[\begin{array}{cc}1& 1\\ 1& 0\end{array}\right]}^n?\left[\begin{array}{c}f(1)\\ f(0)\end{array}\right]=\left[\begin{array}{c}f(n+1)\\ f(n)\end{array}\right]$$

$$令\left[\begin{array}{cc}1& 1\\ 1& 0\end{array}\right]=M$$

此时我们只需要快速的求出$M^n$即可得出$f(n)$

$$假设M^n=\left[\begin{array}{cc}{C}_{00}& C_{01}\\ C_{10}& C_{11}\end{array}\right]$$
最终答案$$f(n)=C_{00}||C_{10}+C_{11}$$

矩阵快速幂题型重点在于

1. 找到递推关系
2. 利用离散化快速求解矩阵M的幂次方

代码如下：

    vector<vector<long long>> multiply(vector<vector<long long>>& a,vector<vector<long long >>b){
        vector<vector<long long>> c(2,vector<long long >(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;
    }
    vector<vector<long long>> pow(vector<vector<long long>>& a,int n){
        vector<vector<long long>> ret={{1,0},{0,1}};
        while(n>0){
        	//矩阵快速幂核心算法(化连续为离散的思想)
        	//例如求A^158
        	//158(10)=10011110(2)
        	//A^158=(A^2)*(A^4)*(A^8)*(A^16)*(A^128)
            if(n&1)
                ret=multiply(ret,a);//以A^158为例，这条语句只会触发5次
            //触发时a的值依次为(A^2)->(A^4)->(A^8)->(A^16)->(A^128)
            n>>=1;
            a=multiply(a,a);//计算每一组的值
        }
        return ret;
    }
    int climbStairs(int n) {
        vector<vector<long long>> ret ={{1,1},{1,0}};
        vector<vector<long long>> res=pow(ret,n);
        return res[0][0];//res[1][0]+res[1][0]也对
    }