Tiling a Rectangle with the Fewest Squares 铺瓷砖

问题描述：

房子的客厅大小为 n x m，为保持极简的风格，需要使用尽可能少的正方形瓷砖来铺盖地面。

假设正方形瓷砖的规格不限，边长都是整数。

请你帮设计师计算一下，最少需要用到多少块方形瓷砖？

n，m 范围[1,13]

分析

这是一个NP-Complete 问题，至于什么是NP问题？我咨询了百度的文心一言，
【NP完全问题是一类复杂的问题，这些问题在多项式时间内没有任何已知的多项式时间算法。换句话说，即使您有一个解决方案，您也无法在多项式时间内验证它的正确性。NP完全问题包括3-SAT，图着色，哈密顿回路，独立集，旅行商问题等。

NP完全问题的难解性在于它们具有NP问题的两个特性：第一，它们可以在多项式时间内验证解决方案是否正确；第二，它们是NP困难的，这意味着不存在多项式时间算法来解决它们。

NP完全问题的难解性意味着，如果有一个NP完全问题可以在多项式时间内解决，那么所有NP问题都可以在多项式时间内解决。因此，解决NP完全问题被认为是计算复杂性的一个重大突破。】

这个问题，之前就看过，很多题解，说的貌似有道理，但是却又无法说明其解法的正确性，官解中给出了一个论文[Minimum tiling of a rectangle by squares],大概意思就是说，想要通过DP做递推解决这个问题，就不要想了。因为在特殊的情况下，你找到的DP方程是失效的，关键是这种特殊的情况，几乎没有规律。这也就导致了，DP在小范围内有效，但是在范围很大的情况下失效。
这就好像在陆地上生活的古人，以自己的生活经验，认为地球是平的，但是大范围内看地球不是平的。总结的规律也就失效了。
这也是NP问题为什么那么复杂的原因，如果你可以在P的时间规模内解决一个NP问题，那么你就是大牛。
回到问题，要求以最少的正方形来铺满，最小的正方形是边长为1。
以h(m,n)表示mn矩阵需要的正方形的最少数量.
论文给出的结论, h(m,n)<max(m,n),这个结论给出正方形的上限。
使用朴素的思路，如果m==n,那么一个正方形就可以解决。否则就需要不停的尝试，这个探索的过程，就可以使用DFS。
为了保证覆盖每个部分，探索的流程，先行后列，而且探索到一个新区域，首先尝试使用允许的最大边长L来铺，一直到边长为1.当铺完当前位置，需要把已铺的区域标记，同时移动到[x,y+L],直到当前行完全铺完，然后进入下一行.

DFS的过程，就是探索每种铺设方案，并且记录其使用瓷砖的数量。

代码

class Solution {int ans;public int tilingRectangle(int n, int m) {ans = Math.max(n, m);boolean[][] rect = new boolean[n][m];dfs(0, 0, rect, 0);return ans;}public void dfs(int x, int y, boolean[][] rect, int cnt) {int n = rect.length, m = rect[0].length;if (cnt >= ans) {return;}        if (x >= n) {ans = cnt; return;}/* 检测下一行 */        if (y >= m) {dfs(x + 1, 0, rect, cnt); return;}        /* 如当前已经被覆盖，则直接尝试下一个位置 */if (rect[x][y]) {dfs(x, y + 1, rect, cnt);return;}for (int k = Math.min(n - x, m - y); k >= 1 && isAvailable(rect, x, y, k); k--) {/* 将长度为 k 的正方形区域标记覆盖 */fillUp(rect, x, y, k, true);/* 跳过 k 个位置开始检测 */dfs(x, y + k, rect, cnt + 1);fillUp(rect, x, y, k, false);}}public boolean isAvailable(boolean[][] rect, int x, int y, int k) {for (int i = 0; i < k; i++) {for (int j = 0; j < k; j++) {if (rect[x + i][y + j]) {return false;}}}return true;}public void fillUp(boolean[][] rect, int x, int y, int k, boolean val) {for (int i = 0; i < k; i++){for (int j = 0; j < k; j++) {rect[x + i][y + j] = val;}}}
}