题解 | #矩形覆盖#

题解一：递归(斐波拉契)
主要思路：最后一块只有竖着和横着两种摆法：即 f(n) = f(n-1) + f(n-2)
递归分析：
递归边界： number = = 0 返回 0； number = 1 只能竖着放返回 1； number = 2 可竖可横返回 2；
递归过程：去计算number-1和number-2
图示：
图片说明

复杂度分析：
时间复杂度： $O(2^N)$ ，每次需要计算f(n-1),f(n-2)
空间复杂度： $O(N)$ ，递归栈深度
实现如下:

class Solution {
public:
    int rectCover(int number) {
        if(number == 0) return 0;
        if(number == 1) return 1; //number =1 只有一种
        if(number == 2) return 2;// number = 2有两种
        return rectCover(number-1) + rectCover(number-2);

    }
};

题解二：记忆化优化递归
题解思路：从上述普通递归中，可以看到 f(n-1) 与 f(n-2) 有很多项(f(3),f(4)...)在之前已经计算过了，可以使用记忆化减少无用计算。
时间复杂度： $O(N)$ ，遍历1~n个小矩阵，计算其中有i数量的矩阵时，摆法数量；
空间复杂度： $O(N)$ ，利用一个标记数组f，以此来记录之前被运算过的使用i个矩阵能摆放的种类数

实现如下:

class Solution {
public:
    int f[1001]{0};  //使用记忆数组，保存已经计算好的值。
    int rectCover(int number) {
        if(number <= 2) return number;
        if(f[number]) return f[number];  //如果之前已经计算过，那么直接返回
        for(int i=3;i<=number;i++)
            f[i] = rectCover(i-1)+rectCover(i-2);
        return f[number];
    }
};

题解三：动态规划+状态压缩
题解思路：同样是应用题解一得出的公式，只是将递归变为迭代的写法。为了最小化空间复杂度，可以使用3个变量完成这个迭代过程。
动态转移方程同题解一：f(n) = f(n-1) +f(n-2)
复杂度分析：
时间复杂度： $O(N)$ ，遍历1~n个小矩阵，计算其中有i数量的矩阵时，摆法数量；
空间复杂度： $O(1)$ ，只是用常数个临时变量存放中间值；

实现如下：

class Solution {
public:
    int rectCover(int number) {
        if(number==0) return 0;
        int a=0,b=1,c;  //使用a,b,c 表示f(n-2),f(n-1),f(n)
        for(int i =1;i<=number;i++)
        {
            c = a + b;  
            a = b;
            b = c;
        }
        return c;
    }
};

相关题目：
跳台阶
 斐波那契数列