题解 | #矩形覆盖#矩阵快速幂乘法解决

这题通过找规律可以发现是一个类似斐波那契数列的二阶问题，常规解法就是使用递归或者改迭代，但是这个复杂度就是O(N)的。
可以有一种矩阵快速幂乘来优化的算法。

    public int rectCover(int target) {
        if(target==0||target==1||target==2) return target;
        /*int preTwo = 1;
        int preOne = 2;
        int temp;
        for(int n = 3;n<=target;n++){
            temp = preOne+preTwo;
            preTwo = preOne;
            preOne = temp;
        }
        return preOne;*/
        //类似斐波那契数列，|F(n),F(n-1)| = |F(2),F(1)|*(二阶矩阵)^(n-2)
        int[][] matrixRes = matrixPow(new int[][]{{1,1},{1,0}},target-2);
        return 2*matrixRes[0][0] + matrixRes[1][0];
    }
    //返回矩阵的n次方,快速幂乘算法
    public int[][] matrixPow(int[][] matrix,int n){
        int[][] temp = null;
        int[][] res = null;
        do{
            temp = temp == null?matrix:matrixMul(temp,temp);
            if((n&1)!=0){
                res = res==null?temp:matrixMul(res,temp);
            }
        }while((n>>>=1)!=0);
        return res;
    }
    public int[][] matrixMul(int[][] mA,int[][] mB){
        int rows = mA.length;
        int cols = mB[0].length;
        int[][] res = new int[rows][cols];
        for(int row = 0;row<rows;row++){
            for(int col = 0;col<cols;col++){
                for(int i = 0;i<mA[0].length;i++){
                    res[row][col] += mA[row][i] * mB[i][col];
                }
            }
        }
        return res;
    }