题解 | #矩形覆盖#

解决这题的突破口是找到递推规律。
根据题目给出的条件，从水平方向看，可以知道，我们竖着摆放21矩形时，必须一次至少摆两个，而横着摆放时，则可以一次摆一个。
所以我们对2n的大矩形，在第一次摆放时，有两种选择，要么摆放一个横着的小矩形，要么一次摆放两个竖着的小矩形。
这样就可以得到递推式f(n)=f(n-1)+f(n-2)。从而得知，本题的递归公式与斐波那契数列一致，属于斐波那契数列的变种。

在面对这种递推题目时，理清思路，找准递推公式是关键。

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