题解 | 矩形覆盖

class Solution {
public:
    int rectCover(int number) {
        if(number==0) return 0;
        if(number==1) return 1;
        int prepre0 = 1, pre0 = 1;
        int cur0;
        for(int i = 2; i <= number; ++i){
            cur0 = pre0+prepre0;
            prepre0 = pre0;
            pre0 = cur0;
        }
        return cur0;
    }
};

因为到上一个状态的列，在只有两行的情况下，两行是相同的，所以只考虑第一行的情况就行，那么只有从前两列中得到，直接相加就行。也就是斐波拉契数列。

时间复杂度O(n)，空间复杂度O(1)。