前言

典型的动态规划问题，可一维dp、二维dp、O(log₂N)的矩阵幂。
先找其中的规律：
只能一步或者两步，比如n==1时，一步结尾的情况等于1，两步结尾的情况等于0。当n等于2时，在一步结尾的基础上加1，再加上在二步结尾的，两者之和就是一步结尾的。而二步结尾的等于原来一步结尾的加1，1+1=2，不算二步结尾的，是因为2+1>2了。
有点抽象，举个例子：
n等于1时，为1 | （无2结尾）；
n等于2时，为11 | 2
n等于3时，为111，21 （以1结尾） | 12（以2结尾，就是11后面这个1+1）
n等于4时，为1111，211，121 | 112（11 1+1），22（2 1+1），122（12 1+1）
…

一、二维dp

1、思想

后者以1结尾的是前者以1结尾+以2结尾（意思就是在后面填个1就可以了）；后者以2结尾的是前者以1结尾的（意思就是只有1+1<=2，2+1>2了，最多跳两步）

2、源码

//二维dp
    public int numWays(int n) {
        if (n == 0 || n == 1)
            return 1;
        int[][] dp = new int[n][2];
        dp[0][0] = 1;
        for (int i = 0; i < n - 1; i++) {
            dp[i + 1][0] = (int) ((long) (dp[i][0] + dp[i][1]) % MOD);
            dp[i + 1][1] = dp[i][0];
        }
        return (int) ((long) (dp[n - 1][0] + dp[n - 1][1]) % MOD);
    }

二、一维dp

1、思想

用上一个dp[0] 去覆盖dp[1]，使其后面用dp[1]时找不到，所以用一个temp去把dp[1]存上。

2、源码

//一维dp
    public int numWays(int n) {
        if (n == 0 || n == 1)
            return 1;
        int[] dp = new int[2];
        dp[0] = 1;
        for (int i = 0; i < n - 1; i++) {
            int temp = dp[1];
            dp[1] = dp[0];
            dp[0] = (int) ((long) (dp[1] + temp) % MOD);
        }
        return (int) ((long) (dp[0] + dp[1]) % MOD);
    }

三、O(log₂N)

1、思想

在这里插入图片描述

在矩阵的左边乘上一个初等矩阵E，E是怎么从单位矩阵I行变换来的，被乘的矩阵也要做相应的行变换，通过递推公式，快速得到最终的变换矩阵，从而快速得到结果。

2、源码

//矩阵法
	static final long MOD = 1000000007;
    static final int[][] E2 = {{1,1},{1,0}};
    public int numWays(int n) {
        if(n == 0 || n == 1){
            return 1;
        }
        int[][] resultM = pow2(n-1);
        return (int)(((long)resultM[0][0] + (long)resultM[1][0])% MOD);
    }
    public int[][] pow2(int n){
        int[][] resultM = {{1,0},{0,1}};
        int[][] tempE = E2;
        while(n>0){
            if((n & 1) == 1){
                resultM = multiply2(resultM,tempE);
            }
            n >>= 1;
            tempE = multiply2(tempE,tempE);
        }
        return resultM;
    }
    public int[][] multiply2(int[][] M1, int[][] M2) {
        int[][] R = new int[2][2];
        for (int i = 0; i < 2; i++) {
            for (int j = 0; j < 2; j++) {
                R[i][j] = (int) (((long) M1[i][0] * M2[0][j] + (long) M1[i][1] * M2[1][j]) % MOD);
            }
        }
        return R;
    }