劍指offer 10 矩形覆蓋

/*我們先把2x8的覆蓋方法記為f(8)，用第一個1x2小矩形去覆蓋大矩形的最左邊時有兩個選擇，豎著放或者橫著放。

當豎著放的時候，右邊還剩下2x7的區(qū)域，這種情形下的覆蓋方法記為f(7)。

當橫著放的時候，當1x2的小矩形橫著放在左上角的時候，左下角必須橫著放一個1x2的小矩形，而在右邊還剩下2x6的區(qū)域，記為f(6)

因此，f(8) = f(7)+f(6)，屬于斐波那契數(shù)列*/

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;
    }
};