题解 | #矩形覆盖#

题目的主要信息：

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

举一反三：

JZ69. 跳台阶

JZ10. 斐波那契数列

JZ71. 跳台阶扩展问题

方法一：递归（推荐使用）

知识点：递归：

递归是一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解。因此递归过程，最重要的就是查看能不能讲原本的问题分解为更小的子问题，这是使用递归的关键。

思路：

首先如果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种。

具体做法：

step 1：约定n等于0时输出0，当n等于1时，只有一种矩形。
step 2：其他情况根据公式 $f (n) = f (n - 1) + f (n - 2)$ ，将两个子问题的结果相加。
step 3：Python版本为了防止超时，需要用数组记录递归中的结果，便于直接使用。

Java实现代码：

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

C++实现代码：

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

Python实现代码：

class Solution:
    def __init__(self):
        self.f = [0] * 40
    
    def rectCover(self , number: int) -> int:
        #约定 n == 0 时，输出 0, 1时也只有一种
        if number <= 2: 
            self.f[number] = number
            return number
        #f(n-1)+f(n-2)
        if self.f[number - 1] == 0:
            self.f[number - 1] = self.rectCover(number - 1)
        if self.f[number - 2] == 0:
            self.f[number- 2] = self.rectCover(number - 2)
        return self.f[number - 1] + self.f[number - 2]

复杂度分析：

时间复杂度： $O (2^{n})$ ，树型递归， $T (n) = T (n - 1) + T (n - 2)$ ，优化后的python版本为 $O (n)$
空间复杂度： $O (n)$ ，递归栈深度为 $n$

方法二：动态规划

知识点：动态规划

动态规划算法的基本思想是：将待求解的问题分解成若干个相互联系的子问题，先求解子问题，然后从这些子问题的解得到原问题的解；对于重复出现的子问题，只在第一次遇到的时候对它进行求解，并把答案保存起来，让以后再次遇到时直接引用答案，不必重新求解。动态规划算法将问题的解决方案视为一系列决策的结果。