剑指offer10：2*1的小矩形横着或者竖着去覆盖2*n的大矩形，总共有多少种方法？

1. 题目描述

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

2.思路和方法

　　思路：（下面说到的x*y的矩形，x是宽，y是长，固定一下方便理解）假设一个2×n的矩形，那么放第一个小矩形有两种放法：放2×1的或者放1×2的，如果是放1×2的意味着在它的下面也只能放一个1×2的，组成一个2×2正方形。那么我们就可以分为两种结构，第一种是2×1的矩形，第二种是2×2的正方形。宽都是2不用考虑，长有1和2两种选择，那么可以将问题转换为：长为n的线段由长为1和长为2的线段组成，共有多少种组成方法。

　　长为n的线段组成方法=（第一步放长为1后剩下的线段的组成方法）+（第一步放长为2后剩下的线段的组成方法），即 f(n)=f(n-1)+f(n-2)；1，2，3，5，8 …。就是一个类似斐波那契数列。

3.C++核心代码

3.1 非递归方法

class Solution {
public:
    int rectCover(int number) {
        if(number<=2)
            return number;
        int f1 = 1;
        int f2 = 2;
        int result = 0;
        for(int i = 3; i <= number; i++){
            result = f1 + f2;
            f1 = f2;
            f2 = result;
        }
        return result;
    }
};

3.2 递归方法

递归代码量少，但是时间复杂度高。对于现在存储空间很大的环境下，应该节约时间。

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

参考资料

https://blog.csdn.net/JMasker/article/details/86771720