题目来源：https://leetcode.cn/problems/qing-wa-tiao-tai-jie-wen-ti-lcof/

引言

动态规划解法，时间复杂度为O(n)O(n)O(n)
使用矩阵乘法快速幂，时间复杂度为 O(logn)O(logn)O(logn)

找规律

f(n)={1,n=0,1f(n−2)+f(n−1),n≥2f(n) = \begin{cases} 1, & n=0,1 \\ f(n-2) + f(n-1), &n \ge2 \end{cases}f(n)={1,f(n−2)+f(n−1),​n=0,1n≥2​

动态规划代码

class Solution {public int numWays(int n) {int a = 1, b = 1, sum;for(int i = 0; i < n; i++){sum = (a + b) % 1000000007;a = b;b = sum;}return a;}
}

矩阵快速幂

分析

改写状态转移公式如下

[f(n)f(n−1)]=[1110][f(n−1)f(n−2)]\begin{bmatrix} f(n) \\ f(n-1) \\ \end{bmatrix} = \begin{bmatrix} 1 & 1\\ 1 & 0\\ \end{bmatrix} \begin{bmatrix} f(n-1) \\ f(n-2) \\ \end{bmatrix} [f(n)f(n−1)​]=[11​10​][f(n−1)f(n−2)​]

以此类推…

[f(n)f(n−1)]=[1110]n−1[f(1)f(0)]\begin{bmatrix} f(n) \\ f(n-1) \\ \end{bmatrix}= \begin{bmatrix} 1 & 1 \\ 1 & 0 \\ \end{bmatrix}^{n-1} \begin{bmatrix} f(1) \\ f(0) \\ \end{bmatrix} [f(n)f(n−1)​]=[11​10​]n−1[f(1)f(0)​]

方阵乘法较为方便改写为如下情况。

[f(n)0f(n−1)0]=[1110]n−1[f(1)0f(0)0]\begin{bmatrix} f(n) & 0\\ f(n-1) & 0\\ \end{bmatrix}= \begin{bmatrix} 1 & 1\\ 1 & 0\\ \end{bmatrix}^{n-1} \begin{bmatrix} f(1) & 0\\ f(0) & 0\\ \end{bmatrix} [f(n)f(n−1)​00​]=[11​10​]n−1[f(1)f(0)​00​]

那么如何快速求得[1110]n\begin{bmatrix} 1 & 1 \\ 1 & 0 \\ \end{bmatrix}^n[11​10​]n即为加速的关键

快速幂

将幂次nnn改写为二进制形式来看，举例当n=5n = 5n=5时，改写为二进制n=0b101n = 0b101n=0b101
那么x5=x22⋅1⋅x21⋅0⋅x20⋅1x^5 = x^{2^2 \cdot 1} \cdot x^{2^1 \cdot 0} \cdot x^{2^0 \cdot 1}x5=x22⋅1⋅x21⋅0⋅x20⋅1
快速幂即可从后往前遍历nnn的二进制数每一位，每比特表示为有效位，每往左迭代1位，乘数平方1次。

Java完整代码

class Solution {static final int MOD = 1000000007;public int numWays(int n) {if (n < 2) {return 1;}int[][] base = {{1, 1}, {1, 0}};int[][] f1f0 = {{1, 1}, {0, 0}};int[][] answer = matrixMultiplication(f1f0, matrixPower(base, n - 1)) ;return answer[0][0];}public int[][] matrixPower(int[][] matrix, int n) {int[][] result = {{1, 0}, {0, 1}};while (n > 0) {if ((n & 1) == 1) {result = matrixMultiplication(matrix, result);}n >>= 1;matrix = matrixMultiplication(matrix, matrix);}return result;}public int[][] matrixMultiplication(int[][] matrix1, int[][] matrix2) {int[][] result = new int[2][2];for (int i = 0; i < 2; ++i) {for (int j = 0; j < 2; ++j) {result[i][j] = (int) (((long) matrix1[i][0] * matrix2[0][j] + (long) matrix1[i][1] * matrix2[1][j]) % MOD);}}return result;}
}