我们可以用2*1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2*1的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法？
思路：还是斐波那契数列思路。考虑一下递推的关系，求n个矩形的方法数为s(n)，想象如果第一个矩形是横着放的，那么此时的方法数就是s(n-1)；如果第一个矩形是竖着放的，那么要想铺满，那么也必须有另一个矩形也竖着放，那么这时候方法数就是s(n-2)。综合起来说，s(n) = s(n-1) + s(n-2);
class Solution { public: int rectCover(int number) { if (number <= 0) return 0; if (number <= 2) return number; return rectCover(number-1) + rectCover(number-2); } };
