题目描述

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

初始代码

class Solution {
public:
    int rectCover(int number) {

    }
};

解题思路

依然还是递归思想。
记待填充的矩形大小为2*n时，总共的填充方法有f(n)种。
那么：

• 若最后填充的小矩形是竖着放的，则只有一种放法；此时f(n)=f(n-1)
• 若最后填充的小矩形是横着放的，则也只有一种放法；f(n)=f(n-2)

综合上面两点，可以得到递推式：f(n) = f(n-1) + f(n-2)

又回到了熟悉的斐波那契递推公式。

多样的代码实现方法可以参见博文剑指OFFER JZ7 斐波那契数列。

下面仅给出最简洁的一种解法：

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

        int a = 1, b = 2;

        for(int i=2; i < number; i++)
        {
            b = a+b;
            a = b-a;
        }
        return b;
    }
};