动态规划

①依题意可知：大矩形的高度固定为2，长度等于小矩形的个数 n。

②确定状态：分析最后一步，假设大矩形长度为 n，其最后一块小矩形可能是竖着摆放的，也可能是横着摆放的；若是竖着的，那么剩余小矩形的面积就为 2×(n-1)；若是横着的，那么其上一块小矩形的位置是确定的，两块小矩形必定会一上一下横着摆放，这两块小矩形的面积为 2×2=4，则其他小矩形的面积为 2×(n-2)。

所以对于 x 个小矩形，若最后一块是横着摆放的，摆法就有 f(x-1)；若是横着摆放的，摆法就有 f(x-2)。

ps：当大矩形长度为 x 时，小矩形一共有 f(x) 种摆法。这里只看长度，因为宽度是固定的。

以2×4为例分析：

摆出长度为1的大矩形，很明显只有1种摆法，即 f(1)=1；

摆出长度为2的大矩形，很明显只有2种摆法，即 f(2)=2；

摆出长度为3的大矩形，假如最后一块是竖着的，那么之前的长度就是2，则 f(3-1)=f(2)=2；假如最后一块是横着的，那么之前的长度就是1，则 f(3-2)=f(1)=1；最后根据加法原则 f(3)=f(3-1)+f(3-2)=3；

摆出长度为4的大矩形，根据上一步的结论，f(4)=f(4-1)+f(4-2)=f(3)+f(2)=3+2=5。

③转移方程：f(x)=f(x-1)+f(x-2)

④初始条件：f(0)=0，f(1)=1，f(2)=2

类似斐波那契数列，唯一的区别是 f(0) 和 f(2)。

维护两个变量来表示f(x-1)和f(x-2)，代替状态数组，将空间复杂度降为O(1)

时间复杂度：O(N)

空间复杂度：O(1)

class Solution
{
    public int rectCover(int number)
    {
        if(number==0 || number==1 || number==2){
            return number;
        }
        int pre1=2; //记录f(x-1)，初始值为f(3-1)
        int pre2=1; //记录f(x-2)，初始值为f(3-2)
        int temp=0; //临时存放pre1的值
        //算出f(number-1)和f(number-2)：
        for(int i=4;i<=number;++i){
            temp=pre1;
            pre1=pre1+pre2;
            pre2=temp;
        }
        return pre1+pre2;
    }
}