LeetCode1240 铺瓷砖

一、问题描述

给定一个大小为 n x m 的长方形，我们需要找出贴满这个矩形所需的整数边正方形的最小数量。例如，当 n = 2，m = 3 时，需要 3 个正方形来覆盖这个长方形，其中包括 2 个 1x1 的正方形和 1 个 2x2 的正方形。

二、解题思路

我们将使用回溯法来解决这个问题。回溯法是一种通过尝试所有可能的解决方案来找到最优解的算法。具体步骤如下：

从长方形的左上角开始，尝试放置不同边长的正方形。
每次放置一个正方形后，更新剩余未覆盖的区域。
递归地继续在剩余区域放置正方形，直到整个长方形被覆盖。
记录并更新使用正方形的最小数量。

三、代码实现

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>// 定义一个全局变量来存储最小正方形数量
int ans;// 回溯函数，尝试不同的正方形填充方式
void dfs(int *h, int n, int m, int squares) {// 如果当前使用的正方形数量已经超过了当前记录的最小数量，直接返回if (squares >= ans) return;int allFilled = 1;// 检查是否所有列都已经被填满for (int i = 0; i < n; i++) {if (h[i] < m) {allFilled = 0;break;}}// 如果所有列都被填满，更新最小正方形数量if (allFilled) {ans = squares;return;}// 找到当前高度最小的列int minH = INT_MAX;int minIndex = -1;for (int i = 0; i < n; i++) {if (h[i] < minH) {minH = h[i];minIndex = i;}}// 尝试不同边长的正方形进行填充for (int w = (n - minIndex < m - minH) ? n - minIndex : m - minH; w > 0; w--) {int canPlace = 1;// 检查是否可以放置边长为 w 的正方形for (int i = minIndex; i < minIndex + w; i++) {if (h[i] + w > m) {canPlace = 0;break;}}if (canPlace) {// 复制当前高度数组，用于回溯int *newH = (int *)malloc(n * sizeof(int));for (int i = 0; i < n; i++) {newH[i] = h[i];}for (int i = minIndex; i < minIndex + w; i++) {newH[i] += w;}// 递归调用 dfs 函数，继续尝试填充dfs(newH, n, m, squares + 1);free(newH);}}
}// 主函数，计算贴满矩形所需的最小正方形数量
int tilingRectangle(int n, int m) {// 如果 n 和 m 相等，只需要一个正方形if (n == m) return 1;// 保证 n 小于等于 m，减少搜索空间if (n > m) {int temp = n;n = m;m = temp;}ans = m;// 初始化高度数组，用于记录每列的填充高度int *h = (int *)calloc(n, sizeof(int));// 调用回溯函数开始搜索dfs(h, n, m, 0);free(h);return ans;
}int main() {int n = 2, m = 3;printf("%d\n", tilingRectangle(n, m));return 0;
}

四、代码解释

1. 全局变量 `ans`

用于存储贴满矩形所需的最小正方形数量。初始时，我们将其设为一个较大的值（这里设为 m），在回溯过程中不断更新这个值。

2. `dfs` 函数

这是回溯函数，它接受四个参数：

h：一个数组，用于记录每列的填充高度。
n：长方形的列数。
m：长方形的行数。
squares：当前已经使用的正方形数量。

在函数内部，首先检查当前使用的正方形数量是否已经超过了 ans，如果是则直接返回。然后检查是否所有列都已经被填满，如果是则更新 ans。接着找到当前高度最小的列，尝试从最大可能的边长开始放置正方形，检查是否可以放置，如果可以则更新高度数组并递归调用 dfs 函数。

3. `tilingRectangle` 函数

这是主函数，它接受两个参数 n 和 m，表示长方形的大小。首先处理特殊情况，如果 n 等于 m，则直接返回 1。然后保证 n 小于等于 m，减少搜索空间。接着初始化 ans 为 m，创建高度数组 h 并初始化为 0，调用 dfs 函数开始回溯搜索，最后释放 h 数组占用的内存并返回 ans。

4. `main` 函数

在 main 函数中，我们定义了一个示例输入 n = 2，m = 3，调用 tilingRectangle 函数计算结果并输出。

五、复杂度分析

时间复杂度：由于使用了回溯法，最坏情况下需要尝试所有可能的正方形放置方式，时间复杂度为 $O(2^{n*m})$ 。
空间复杂度：主要是递归调用栈的空间和动态分配数组的空间，空间复杂度为O(n)。

六、总结

通过回溯法，我们可以解决用整数边正方形贴满长方形的最小数量问题。虽然这种方法在最坏情况下的时间复杂度较高，但对于较小的输入规模是可行的。在实际应用中，我们可以根据具体情况对算法进行优化，以提高效率。

希望这篇博客能帮助你理解如何使用 C 语言解决这个有趣的问题！如果你有任何疑问或建议，欢迎留言讨论。