题解 | #矩形覆盖#

class Solution {
public:
    int rectCover(int number) {
       //我们用2x1的小矩形横着或者竖着去覆盖更大的矩形。请问用2x1的小矩形无重叠地覆盖一个2xn的大矩形，从同一个方向看总共有多少种不同的方法？
        if(number == 0)
        {
            return 0;
        }
        if(number == 1){
            return 1;
        }
        if(number == 2){
            return 2;
        }
        int fn_1 = 2;
        int fn_2 = 1;
        int fn = fn_1 + fn_2;
        for(int i  = 3;i<=number;i++)
        {
           fn = fn_1 + fn_2;
           fn_2 = fn_1;
           fn_1 = fn;
        }
        return fn; 

    }

};

本题是一个特殊的斐波拉契数列。

n = 1, f(n) = 1;

n = 2, f(n) = 2;

n >= 3, f(n) = f(n-1) + f(n-2);

记住就好了。