铺瓷砖

难度:

标签:

题目描述

Given a rectangle of size n x m, return the minimum number of integer-sided squares that tile the rectangle.

Example 1:

Input: n = 2, m = 3
Output: 3
Explanation: 3 squares are necessary to cover the rectangle.
2 (squares of 1x1)
1 (square of 2x2)

Example 2:

Input: n = 5, m = 8
Output: 5

Example 3:

Input: n = 11, m = 13
Output: 6

Constraints:

1 <= n, m <= 13

代码结果

运行时间: 33 ms, 内存: 16.0 MB

/*
 * 思路：使用动态规划来解决最少瓷砖覆盖问题。
 * 使用Java Stream API进行优化计算。
 * 初始化dp数组，当i或j为0时，dp[i][j]为0，因为不需要任何瓷砖。
 */
import java.util.stream.IntStream;
public class Solution {
    public int tilingRectangle(int n, int m) {
        if (n == m) return 1;
        int[][] dp = new int[n + 1][m + 1];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                final int I = i, J = j;
                dp[i][j] = IntStream.rangeClosed(1, Math.min(I, J)).parallel()
                        .map(k -> 1 + dp[I - k][J] + dp[I][J - k] + dp[I - k][J - k])
                        .min().orElse(Integer.MAX_VALUE);
            }
        }
        return dp[n][m];
    }
}

解释

方法:

此题解采用了动态规划的方法来解决问题。定义 dp[i][j] 为铺满 i x j 的矩形所需要的最小瓷砖数。初始化所有的 dp[i][j] 为无穷大（即一个很大的数），表示尚未计算。基础情况是当 i = j 时，即矩形为正方形时，只需要一块 i x i 的瓷砖，因此 dp[i][j] = 1。接下来，对于不同的矩形尺寸，通过尝试所有可能的水平或垂直切割来更新 dp[i][j] 的值。水平切割意味着将矩形分成上下两部分，垂直切割则是左右两部分。对于每种切割，dp 值是两个子矩形所需瓷砖数的和的最小值。通过这种方法，可以逐步构建出所有 dp[i][j] 的值，最终 dp[m][n] 就是所求结果。

时间复杂度:

O(m * n * (n + m))

空间复杂度:

O(m * n)

代码细节讲解

🦆

为什么在动态规划的解法中，初始化所有dp[i][j]为无穷大？

▷

在动态规划中，初始化 dp[i][j] 为无穷大是为了确保在后续的计算过程中，当我们尝试找到铺满 i x j 矩形的最小瓷砖数时，可以通过比较和取最小值的方式来更新 dp[i][j]。如果初始值不是无穷大，可能会导致计算结果不准确，因为任何非无限大的初始值可能会低估所需的瓷砖数量。无穷大作为初始值确保了只有通过具体操作得到的值才会被考虑进最终的结果。

🦆

题解中提到当i = j时，即矩形为正方形，dp[i][j]设为1。这种初始化方法是否适用于所有正方形，无论其大小？

▷

是的，这种初始化方法适用于所有大小的正方形。当矩形的长度和宽度相等时，即形成一个正方形，最简单且最小的铺瓷砖方式是使用一块与该正方形相同大小的瓷砖。因此，对于任何 i = j 的情况，dp[i][j] 被设置为 1，表示只需要一块 i x i 的瓷砖就能完全铺满该正方形。

🦆

动态规划的方法中，如何选择进行水平切割还是垂直切割？什么情况下会选择水平切割，什么情况下会选择垂直切割？

▷

在动态规划的解法中，选择水平切割还是垂直切割取决于哪种切割方式能够得到最小的瓷砖数。水平切割将矩形沿水平方向分成上下两部分，而垂直切割则将其分为左右两部分。算法会尝试所有可能的水平和垂直切割位置，计算每种切割后两部分所需瓷砖数的和，并更新 dp[i][j] 为这些值中的最小值。通常，如果矩形的长大于宽，倾向于进行水平切割来减少较长的维度；如果宽大于长，则可能倾向于进行垂直切割。但最终的选择完全基于哪种方式可以最小化所需的瓷砖数。

铺瓷砖

题目描述

代码结果

解释

代码细节讲解

相关问题