【剑指offer】矩形覆盖

经典题，思想很好，小白可以多读几遍分析思路！（P79）

class Mat { // 矩阵对象
    int n = 2;
    int m[][] = new int[n][n];

    public Mat mul(Mat a) { // 矩阵乘法
        Mat b = new Mat();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++)
                for (int k = 0; k < n; k++)
                    b.m[i][j] += this.m[i][k] * a.m[k][j];
        }
        return b;
    }
}

public class Solution {
    public int RectCover(int target) {
        if(target==0){
            return 0;
        }

        Mat ans = new Mat();
        for (int i = 0; i < ans.n; i++) { //单位矩阵初始化
            ans.m[i][i] = 1;
        }
        Mat base = new Mat();
        base.m[0][0] = base.m[0][1] = base.m[1][0] = 1; // base矩阵初始化
        base.m[1][1] = 0;

        target -= 1;
        while (target > 0) { // 快速幂：求base矩阵的n-1次方
            if ((target & 1) != 0) {
                ans = ans.mul(base);
            }
            target >>= 1;
            base = base.mul(base);
        }
        return ans.m[0][0]+ans.m[0][1];

    }
}