[矩阵快速幂] 爬楼梯

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

示例 1：

输入：n = 2
输出：2
解释：有两种方法可以爬到楼顶。
1. 1 阶 + 1 阶
2. 2 阶

示例 2：

输入：n = 3
输出：3
解释：有三种方法可以爬到楼顶。
1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶

解题分析

爬楼梯的话其实蛮明显的一个递推关系，dp[i]=dp[i-1]+dp[i-2]; 不过这样的话其实很容易发现一个问题，一旦数据过大就会导致C++ 原本的int或者long long 超类型。然后时间复杂度也达到了O(n)。那么有没有什么更快的方法可以快一些得到答案呢。我们观察这个递推公式，很容易想到一个矩阵。矩阵的特点是第一行都是dp[i-1]和dp[i-2]前面的系数，也就是{1,1}。矩阵的左下角的降阶矩阵是一个单位矩阵，也就是对角线上都是1。对于二阶矩阵而言，就是{{1,1},{1,0}},用这个矩阵乘上矩阵{{f(n)},{f(n-1)}}。可以得到矩阵{{f(n+1)},{f(n)}}。也就是说，我们不断递推的话可以得到一个很好看的公式{{f(n+1)},{f(n)}}=({{1,1},{1,0}})^n*{{f(1)},{f(0)}}。所以说，我们只需要去求出一个矩阵的n次幂，然后利用这个递推公式很快就能求出f(n)了。但是呢，如果我们之间去求矩阵的次幂，那也会导致时间复杂度过高。有没有什么办法？当然有，那就是矩阵快速幂。我们可以想，如果我们要求一个矩阵A的10次方，我们先把10转换为二进制1010，现在，我们可以进入一个循环，判断条件是n=1010(2)大于0。我们每次进入循环判断n的最后一位是不是1，如果是，我们就用ret（初始化为一个单位矩阵）乘上A；如果不是，我们啥也不做。然后我们令n>>=1; 之后我们让A*=A。也就是自己倍乘一下。这样，循环结束后我们得到的矩阵ret就是A的n次方啦，而且很明显时间的复杂度为O(logn)，相比较原来的时间复杂度可以说有巨大的提升。最后，我们根据矩阵乘法的关系直接输出答案即可。

代码实现

class Solution {
public:vector<vector<long long>> multiply(vector<vector<long long>>& a,vector<vector<long long>>& b,int n=2){vector<vector<long long>> c(n,vector<long long>(n));for(int i=0;i<n;i++){for(int j=0;j<n;j++){c[i][j]=0;for(int k=0;k<n;k++){c[i][j]+=a[i][k]*b[k][j];}}}return c;}vector<vector<long long>> matrixPow(vector<vector<long long>> a, int n) {vector<vector<long long>> ret = {{1, 0}, {0, 1}};while (n > 0) {if ((n & 1) == 1) {ret = multiply(ret, a);}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 = matrixPow(ret, n);return res[1][0]+res[1][1];}
};