JZ70: 矩形覆盖

[songyy5517]

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

注意：约定 n == 0 时，输出 0

比如n=3时，2*3的矩形块有3种不同的覆盖方法(从同一个方向看)：

输入描述： 2*1的小矩形的总个数n

返回值描述： 覆盖一个2*n的大矩形总共有多少种不同的方法(从同一个方向看)

示例1

输入：0
返回值：0

示例2

输入：1
返回值：1

示例3

输入：4
返回值：5

分析 这道题需要我们求n个小矩形的摆法数。当n=1时，共有1中；当n=2时，有两种摆法。当有n个小矩形时，考虑将第一个矩形竖直摆放，我们可以将整个部分看成最左边的1个矩形 + 后面的n-1个矩形:

考虑将第一个矩形水平摆放，则还需要另一个矩形进行补充，因此整个部分可看成最左边的2个矩形 + 后面的n-2个矩形:

因此我们可以使用动态规划来解决问题。

[songyy5517]

思路：动态规划

1. 异常处理（n = 0, 1, 2）；
2. 状态定义 & 初始化；
   • f_1 = 2: 上一个状态；
   • f_2 = 1: 上上个状态；
   • res: 最终结果。
3. 自下而上求各个状态；
   • 状态转移方程：res = f_1 + f_2;
   • 更新变量。
4. 返回最终结果res。

复杂度分析

• 时间复杂度： $O(N)$ ，计算状态一共要进行 $N - 3$ 次循环，使用 $O(N)$ 大小的时间；
• 空间复杂度： $O(1)$ ，额外定义了常数大小的变量。

[songyy5517]

import java.util.*;
public class Solution {
    public int rectCover(int target) {
        // 思路：动态规划。难点在于确定状态转移方程。
        // 1. 异常处理
        if (target <= 2)
            return target;

        // 2. 状态定义
        int f_1 = 2, f_2 = 1;
        int res = 0;

        for (int i = 3; i <= target; i++){
            res = f_1 + f_2;
            f_2 = f_1;
            f_1 = res;
        } 

        return res;
    }
}

[songyy5517]

2024/4/30