题解 | #矩形覆盖#

描述
我们可以用21的小矩形横着或者竖着去覆盖更大的矩形。请问用n个21的小矩形无重叠地覆盖一个2n的大矩形，从同一个方向看总共有多少种不同的方法？
比如n=3时，23的矩形块有3种不同的覆盖方法(从同一个方向看)：

输入描述：
2*1的小矩形的总个数n
返回值描述：
覆盖一个2*n的大矩形总共有多少种不同的方法(从同一个方向看)
示例1
输入：
0
返回值：
0
示例2
输入：
1
返回值：
1
示例3
输入：
4
返回值：
5

递归：

class Solution {
public:
    int rectCover(int number) {
        if (number < 3) return number;
        return rectCover(number-1) + rectCover(number-2); // 递归
    }
};

动态规划：

class Solution {
public:
    int rectCover(int number) {
        if (number < 3) return number;
        else {
            int dp1 = 3, dp2 = 2, dp;  // 动态规划
            for (int i = 4; i <= number; ++i) {
                dp = dp1 + dp2;
                dp2 = dp1;
                dp1 = dp;
            }
            return dp;
        }
    }
};