剑指offer 10 矩形覆盖

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

/*我们先把2x8的覆盖方法记为f(8)，用第一个1x2小矩形去覆盖大矩形的最左边时有两个选择，竖着放或者横着放。

当竖着放的时候，右边还剩下2x7的区域，这种情形下的覆盖方法记为f(7)。

当横着放的时候，当1x2的小矩形横着放在左上角的时候，左下角必须横着放一个1x2的小矩形，而在右边还剩下2x6的区域，记为f(6)

因此，f(8) = f(7)+f(6)，属于斐波那契数列*/

class Solution {
public:
    int rectCover(int number) {
		if(number==1){
            return 1;
        }
        if(number==2){
            return 2;
        }
        
        int first=1;
        int second=2;
        int sum=0;
        for(int i=3;i<=number;i++){
            sum=first+second;
            first=second;
            second=sum;
        }
        
        return sum;
    }
};