https://leetcode-cn.com/problems/climbing-stairs/solution/pa-lou-ti-by-leetcode-solution/

Idea

这个题其实就是斐波那契数列
初始条件F[1]=1 F[2]=2
dp方程为

对于这样的方程 我们可以用动态规划写出一个时间空间复杂度都为的算法

但是 对与这样的一次线性递推方程 我们可以用滚动数组来优化空间复杂度

Code

class Solution {
    public int climbStairs(int n) {
        int p = 0, q = 0, r = 1;
        for (int i = 1; i <= n; ++i) {
            p = q; 
            q = r; 
            r = p + q;
        }
        return r;
    }
}

优化思路

对于斐波那契数列的递推方程 我们可以用矩阵表示为

由于此题中F[1]=1 F[2]=2
可以得到

又因为 矩阵的值有一个特性 就是 c+d=a
因此当矩阵乘以[1,1]的时候 可以直接再乘以一个矩阵来替代 也就是直接求矩阵的n次方就可以了

因此 我们可以用矩阵快速幂把这道题优化到

public class Solution {
   public int climbStairs(int n) {
       int[][] q = {{1, 1}, {1, 0}};
       int[][] res = pow(q, n);
       return res[0][0];
   }
   public static int[][] pow(int[][] a, int n) {
        int[][] ret = {{1, 0}, {0, 1}}; //单位矩阵
        while (n > 0) {
            if ((n & 1) == 1) { //(n & 1) == 1 判断n是否为奇数 n为奇数的话二进制最低位一定为1  1 and 1还是1
                ret = multiply(ret, a);
            }
            n >>= 1; //>> 右移运算符 比如n=77=1001101 右移之后 变成100110
            a = multiply(a, a); //同时 a需要对自己进行平方 因为右移之后 相当于增加了2的平方
        }
        return ret;
    }
   public int[][] multiply(int[][] a, int[][] b) {
       int[][] c = new int[2][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;
   }
}