题解 | #矩形覆盖#

题目的主要信息：

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

举一反三：

JZ69. 跳台阶

JZ10. 斐波那契数列

JZ71. 跳台阶扩展问题

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

知识点：递归：

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

思路：

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

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

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

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

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

由规律发现，$2\ast n2*n$的矩形的情况数为$f(n)=f(n-1)+f(n-2)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)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)O(2^n)$，树型递归，$T(n)=T(n-1)+T(n-2)T(n)=T(n-1)+T(n-2)$，优化后的python版本为$O(n)O(n)$
• 空间复杂度：$O(n)O(n)$，递归栈深度为$nn$

方法二：动态规划

知识点：动态规划

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

思路：

对于斐波那契数列的递推公式：$f(n)=f(n-1)+f(n-2)f(n)=f(n-1)+f(n-2)$，除了自顶向下递归求解，还可以直接自底向上相加，递归的本质是从顶部往下找，然后再向上相加，我们可以使用动态规划直接相加。

dp[1] = 1;
dp[2] = 2;
for(int i = 3; i <= number; i++)
    dp[i] = dp[i - 1] + dp[i - 2]; //公式不断相加

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

res = dpi_1 + dpi_2; //公式相加
dpi_2 = dpi_1; //变量更新
dpi_1 = res;

具体做法：

• step 1：约定n等于0时输出0，当n等于1时，只有一种矩形。
• step 2：初始化两个变量。
• step 3：遍历到目标数字number，两个变量交替滚动相加得到结果。

Java实现代码：

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

C++实现代码：

class Solution {
public:
    int rectCover(int number) {
        //约定 n == 0 时，输出 0, 1时也只有一种
        if(number <= 2) 
            return number;
        //初始化n=1
        int dpi_2 = 1; 
        //初始化n=2
        int dpi_1 = 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;
    }
};

Python实现代码：

class Solution:
    def rectCover(self , number: int) -> int:
        #约定 n == 0 时，输出 0, 1时也只有一种
        if number <= 2:
            return number
        #初始化n=1
        dpi_2 = 1
        #初始化n=2
        dpi_1 = 2 
        res = 0
        for i in range(3, number + 1):
            #公式相加
            res = dpi_1 + dpi_2 
            #变量更新
            dpi_2 = dpi_1
            dpi_1 = res
        return res

复杂度分析：

• 时间复杂度：$O(n)O(n)$，一次遍历
• 空间复杂度：$O(1)O(1)$，常数级变量，无额外辅助空间