题解 | 矩形覆盖

class Solution {
    //题目说得大矩阵是2*n的，小矩阵是2*1；然后多少种改变，可以发现其改变拆分成很多个的两个小矩阵的改变（倒一下），改变方式相同，只是位置不同，所以可以分改变的个数不同情况讨论，同时往下加个数，递归计算；
public:
    int res=1;

    int rectCover(int number) {
        if(number == 0) return 0;

        dp(number, 1);

        return res;
    }

    void dp(int number, int start){
        if(number-start+1<2){
            return;
        }

        res  += number - start;
        for(int i = start; i<=number-1; ++i){
            dp(number, i+2);
        }
    }
};