矩形覆盖（C++）

  我们可以用 2*1 的小矩形横着或者竖着去覆盖更大的矩形。请问用 n 个 2*1 的小矩形无重叠地覆盖一个 2*n 的大矩形，从同一个方向看总共有多少种不同的方法？

数据范围：0≤n≤38
进阶：空间复杂度 O(1) ，时间复杂度 O(n)

注意：约定 n == 0 时，输出 0

比如n=3时，2*3的矩形块有3种不同的覆盖方法(从同一个方向看)：

2*1的小矩形的总个数n

覆盖一个2*n的大矩形总共有多少种不同的方法(从同一个方向看)

输入：
0
返回值：
0

输入：
1
返回值：
1

输入：
4
返回值：
5

根据题意可知，除去n==0的情况，当n == 1时，覆盖方法有1种；当n == 2时，覆盖方法有2种；当n == 3时，覆盖方法有1+2 = 3种，当n == 4时，覆盖方法有2+3 = 5种…，即规律为（或者说状态转移方程）dp[i] = dp[i-1] + dp[i-2]。dp[i]表示2*1的小矩形总数为i时，共有多少总覆盖方法。

class Solution {
public:
    int rectCover(int number) {
        if(number == 0 || number == 1 || number == 2)
            return number;
        int a = 1;
        int b = 2;
        int res = a + b;
        for(int i = 3; i < number;i++)
        {
            a = b;
            b = res;
            res = a + b;
        }
        return res;
    }
};

利用递归求解，思路与方式一类似。

class Solution {
public:
    int rectCover(int number) {
        if(number == 0 || number == 1 || number == 2)
            return number;
        return rectCover(number -1) + rectCover(number - 2);
    }
};