跳台阶问题(类似斐波那契数列)

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

引言

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

找规律

f ( n ) = { 1 , n = 0 , 1 f ( n − 2 ) + f ( n − 1 ) , n ≥ 2 f(n) =

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;
    }
}
1
2
3
4
5
6
7
8
9
10
11

矩阵快速幂

分析

改写状态转移公式如下

[ f ( n ) f ( n − 1 ) ] = [ 1 1 1 0 ] [ f ( n − 1 ) f ( n − 2 ) ]

= [f(n)f(n−1)​]=[11​10​][f(n−1)f(n−2)​]

以此类推…

[ f ( n ) f ( n − 1 ) ] = [ 1 1 1 0 ] n − 1 [ f ( 1 ) f ( 0 ) ]

= ^{n-1} [f(n)f(n−1)​]=[11​10​]n−1[f(1)f(0)​]

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

[ f ( n ) 0 f ( n − 1 ) 0 ] = [ 1 1 1 0 ] n − 1 [ f ( 1 ) 0 f ( 0 ) 0 ]

= ^{n-1} [f(n)f(n−1)​00​]=[11​10​]n−1[f(1)f(0)​00​]

那么如何快速求得 [ 1 1 1 0 ] n

^n [11​10​]n即为加速的关键

快速幂

将幂次$n$改写为二进制形式来看，举例当$n=5$时，改写为二进制$n=0b101$
那么$x^5=x^{2^2\cdot 1}\cdot x^{2^1\cdot 0}\cdot x^{2^0\cdot 1}$
快速幂即可从后往前遍历$n$的二进制数每一位，每比特表示为有效位，每往左迭代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;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37