题目主要信息

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

2、约定 n == 0 时，输出 0

3、进阶要去空间复杂度O(1)，时间复杂度O(n);

方法一：递归

具体方法

通过几个示例

我们可以看出，本题考查的是斐波那契数列的dp[n] = dp[n-1]+dp[n-2]

Java代码

public class Solution {
    public int rectCover(int target) {
        if(target<=2){
            return target;
        }
        return rectCover(target-1)+rectCover(target-2);
    }
}

复杂度分析

时间复杂度：$O((\mathrm{（}1+\sqrt{5}\mathrm{）}\mathrm{/}2{)}^n)O((（1+\backslash sqrt\{5\}）/2)^n)$,在递推的求解过程中会出现循环的嵌套，

F(n)= F(n-1)+F(n-2)

我们把计算F(i)所需要的时间记为T(i)。然后记计算加法所需的时间为1，那么显然有

T(n) = 1+ T(n-1)+T(n-2)

这一式子可以进行变形，两边同时加1，得到

T(n)+1 = (T(n-1)+1)+(T(n-2)+1)

记T(n)+1=A(n),那么显然

A(n)=A(n-1)+A(n-2)

这是一个斐波那契数列，只不过初项有所不同。

但是斐波那契数列的增长率与初项无关。证明如下：

设某斐波那契数列的前两项为a,b,令c=max(a,b),显然这个数列的增长速度不会超过以c为初项的斐波那契数列。 那么显然，以c为初项的斐波那契数列，它的元素是

空间复杂度：$O(n)O(n)$，在递归的过程中保存了 结果

方法二：迭代优化

具体方法

可以推导一下公式

f(0) = 1

f(1) = 1

f(2) = 2

f(3) = 3

f(4) = 5 = f(2)+f(3)

f(5) = 8 = f(3)+f(4)

...

f(n) = f(n-1)+f(n-2)

Java代码

public class Solution {
    public int rectCover(int target) {
        int a = 1,b = 2;
        if(target <=2) return target;
        int sum = 0;
        for(int i=3;i<=target;i++){
            sum = a+b;
            a = b;
            b = sum;
        }
        return sum;
    }
}

###复杂度分析

• 时间复杂度：$O(n)O(n)$，一次遍历即可
• 空间复杂度：$O(1)O(1)$，临时变量sum