剑指Offer：矩形覆盖

矩形覆盖

1. 问题描述
我们可以用2 x 1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2 x 1的小矩形无重叠地覆盖一个2 x n的大矩形，总共有多少种方法？
比如n=3时，2 x 3的矩形块有3种覆盖方法：

2. 解题思路
①：假如现在有一个2 x n的矩形，n>2。
②：第一次用小矩形去覆盖的时候，有两种选择：横着放或者竖着放
#横着放：横着放的话，如果在上面放，下面那个区域也只能横着放，所以横着放完还剩下2 x (n-2)个格子
#竖着放：竖着放的话，还剩下2 x (n-1)个格子
③：所以很容易得出，f(n) = f(n-1)+f(n-2)，是不是很熟悉 ↓
④：实际上得出的就是一个类似于斐波那契数列表达式，并且f(1) = 1,f(2) = 2.
⑤：斐波那契数列：https://blog.csdn.net/qq_42714490/article/details/104755197
⑥：图解：

3. c/c++源代码

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

4. 留言
CSDN：https://blog.csdn.net/qq_42714490
欢迎交流：

作者：有梦想的阿长
微信：hs835844948
【转载文章务必保留出处和署名，谢谢！】