题解 | #矩形覆盖#

第四十五题 动态规划 考虑往后递归的递归的条件

class Solution {
public:
    int rectCover(int number) {
        // 拼接完number个1*2 的矩阵 使其拼完是个矩阵2*n
        // 因为限定了 拼好的矩阵 高度还是2，所以难度降低了，只能在拓展长度的时候变
        // 前两种比较特殊 因为如果结果是2，那么可以叠加起来
        if(number <=2) return number;
        int *a=new int[number+1];
        a[0]=1;a[1]=1;a[2]=2;
        for(int i=3;i<=number;i++)
            // 比他少一块的 直接在一边加一块 所以a[i-1]
            // 比他少两块的，因为是两个1*2 所以两个叠起来是2*2 所以 差两个的时候 可以再用不同的两个叠加方式算进去
            a[i]=a[i-1]+a[i-2];
//         for(int i=3;i<=number;i++)
//         {
//             cout<<a[i]<<endl;
//         }
        return a[number];
    }
};