题解 | #跳台阶# 矩阵快速幂，O(logn) 复杂度

由于算法的限制只有 40，若如果数字远大，例如 target = 2^30 次，则可以用此法来解决。

public class Solution {
    public int jumpFloor(int target) {
        if (target <= 2) {
            return target;
        }
        Matrix a = initMatrix();
        a = Matrix.pow(a, target-2);
        Matrix b = new Matrix(2, 1);
        b.arr[0][0] = 2;
        b.arr[1][0] = 1;
        b = Matrix.mult(a, b);
        return b.arr[0][0];
    }
    
    public Matrix initMatrix() {
        Matrix matrix = new Matrix(2, 2);
        matrix.arr[0][0] = 1;
        matrix.arr[0][1] = 1;
        matrix.arr[1][0] = 1;
        return matrix;
    }
}

class Matrix {
    int m, n;
    int[][] arr;
    public Matrix(int m, int n) {
        this.m = m;
        this.n = n;
        this.arr = new int[m][n];
    }
    
    public static Matrix mult(Matrix matrix1, Matrix matrix2) {
        int m = matrix1.m, n = matrix2.n;
        Matrix matrix = new Matrix(m, n);
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                for (int k = 0; k < matrix1.n; k++) {
                    matrix.arr[i][j] += matrix1.arr[i][k] * matrix2.arr[k][j];
                }
            }
        }
        return matrix;
    }
    
    public static Matrix pow(Matrix matrix, int n) {
        Matrix x = matrix;
        n -= 1;
        while (n != 0) {
            if ((n & 1) == 1) {
                matrix = mult(x, matrix);
            }
            x = mult(x, x);
            n >>= 1;
        }
        return matrix;
    }
}