题目的主要信息：

可以用 $2 * 1$ 的小矩形横着或者竖着去覆盖更大的矩形
若用n个 $2 * 1$ 的小矩形无重叠地覆盖一个 2*n 的大矩形，从同一个方向看总共有多少种不同的方法
注意：约定 n == 0 时，输出 0
进阶要求：时间复杂度： $O (n)$ ，空间复杂度： $O (1)$

思路：

首先如果n=0，则只有0种；

如果n=1，也只有1种；

如果n=2，有横竖2种情况：

alt

如果n=3，有3种情况： alt

而如果n=4，有5种情况： alt

由规律发现， $2 * n$ 的矩形的情况数为 $f (n) = f (n - 1) + f (n - 2)$ ，即这就是一个斐波那契数列，按照斐波那契数列的解法来即可，需要注意不同点在于n小于等于2时，都只有n种。

方法一：递归

具体做法：

class Solution {
public:
    int rectCover(int number) {
        if(number <= 2) //约定 n == 0 时，输出 0, 1时也只有一种
            return number;
        return rectCover(number - 1) + rectCover(number - 2);//f(n-1)+f(n-2)
    }
};

复杂度分析：

时间复杂度： $O (n^{2})$ ，树型递归， $T (n) = T (n - 1) + T (n - 2)$
空间复杂度： $O (n)$ ，递归栈深度为树最深处，

方法二：动态规划

具体做法：

对于斐波那契数列的递推公式： $f (n) = f (n - 1) + f (n - 2)$ ，我们可以用dp数组动态规划不断相加得到。

class Solution {
public:
    int rectCover(int number) {
        if(number <= 2) //约定 n == 0 时，输出 0, 1时也只有一种
            return number;
        vector<int> dp(number + 1); 
        dp[1] = 1;
        dp[2] = 2;
        for(int i = 3; i <= number; i++)
            dp[i] = dp[i - 1] + dp[i - 2]; //公式不断相加
        return dp[number];
    }
};

但是这个方法使用了dp数组，空间复杂度为 $O (n)$ ，不满足要求，因此我们对空间优化一下：注意到每次循环只使用到了第 $i - 1$ 个变量和第 $i - 2$ 个变量，那我们可以用两个变量不断滚动来优化。

class Solution {
public:
    int rectCover(int number) {
        if(number <= 2) //约定 n == 0 时，输出 0, 1时也只有一种
            return number;
        int dpi_2 = 1; //初始化n=1
        int dpi_1 = 2; //初始化n=2
        int res = 0;
        for(int i = 3; i <= number; i++){
            res = dpi_1 + dpi_2; //公式相加
            dpi_2 = dpi_1; //变量更新
            dpi_1 = res;
        }
        return res;
    }
};

复杂度分析：

时间复杂度： $O (n)$ ，一次遍历
空间复杂度： $O (1)$ ，常数级遍历

题解 | #矩形覆盖#

题目的主要信息：

思路：

方法一：递归

方法二：动态规划