题目描述

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

数据范围：0≤n≤38
进阶：空间复杂度O(1) ，时间复杂度O(n)
注意：约定 n == 0 时，输出 0 比如n=3时，2 * 3的矩形块有3种不同的覆盖方法(从同一个方向看).

图示采用某位大佬，在此引用

斐波那契数列
由图示可知，是典型的斐波那契数列

代码

class Solution {
public:
    int rectCover(int number) {
        //当n = 0，f(0) = 0;
        //当n = 1，f(1) = 1;
        //当n = 2，f(2) = 2;
        //当n = 3，f(3) = 3;
        //当n = 4，f(4) = 5;
        //当n>2时候，f(n) = f(n-1)+f(n-2);
        //典型的斐波那契数列
        //题解：动态规划
        if(number <=3) return number;
        int a = 1;
        int b = 2;
        int sum = 0;
        for(int i =2;i<number;i++){
            sum = b+a;
            a = b;
            b = sum;
        }
        return sum;
    }
};