LEETCODE 1240. Tiling a Rectangle with the Fewest Squares 解题思路分析

题目大意：

铺瓷砖

你是一位施工队的工长，根据设计师的要求准备为一套设计风格独特的房子进行室内装修。

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

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

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

示例 1：

输入：n = 2, m = 3
输出：3
解释：3 块地砖就可以铺满卧室。
     2 块 1x1 地砖
     1 块 2x2 地砖

示例 2：

输入：n = 5, m = 8
输出：5

示例 3：

输入：n = 11, m = 13
输出：6

提示：

• 1 <= n <= 13
• 1 <= m <= 13

---

如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1240

解题思路分析：

在铺设瓷砖时，当前正方形的尺寸需要使用多大才能使全局最优，这是我们当前无法直接判断出来的，因此只能一种一种的去尝试，每做出一种尝试，我们将剩余的空地交给递归子问题去解决，子问题中同样要在剩余的空地上做出尝试，直到将所有地面铺满，在所有方式中找到一个最优解即可。这是典型的递归思路。之前的文章多次讲过，使用递归方法其实与动态规划DP没有本质上的区别，个人认为递归更好理解，因此本题也使用递归方式来解题。

解题时，上面的思路使我们的核心思想，通常情况下，使用递归要配合记忆数组来优化效率。使用记忆数组本质上是为了减少重复性的计算，不过本题我实在是没有找到合适的方式来存储记忆数组。因此只能在剪枝上下功夫。

因为要求最小值，我们可以保存一个全局变量，每递归完一个分支，都更新一下当前结果中的最小值，后续递归执行时，如果某个阶段的结果已经大于等于这个最小值，可以提前终止递归。除此之外，还有一点可以优化，在我们选择当前点所有可以摆放的正方形中，从最大的开始选择会更好一些。

看下实现代码：

int min=Integer.MAX_VALUE; // 返回结果，先设个最大值
public int tilingRectangle(int n, int m) {
    if(m==n) return 1; // 如果长宽相同，即是正方形，返回1
    helper(new int[n][m],0,0,0); // 递归找最优解
    return min;
}
// visited表示哪些格子已经放入正方形
// row和col代表当前点的坐标
// count为到目前为止已经摆放了几个正方形
private void helper(int[][]visited,int row,int col, int count){
    // 如果当前的count已经大于等于之前的最小值，那没有必要继续摆放下去
    if(count>=min) return;
    // 从当前点开始循环，找到下一个还没摆放的点
    for(int r=row;r<visited.length;r++){
        for(int c=col;c<visited[0].length;c++){
            // 如果当前点已经摆放过，就跳过
            if(visited[r][c]==1) continue;
            // 以当前点为起点，向右下方向理论上能画出的最大正方形边长
            int lengthMax = Math.min(visited.length-r, visited[0].length-c);
            // 从最大边长循环到1画正方形
            for(int i=lengthMax;i>=1;i--){
                // 如果当前正方形区域内存在以访问过的点，跳过，缩小正方形边长
                if(!findRectangle(visited, r, c, i)) continue;
                // 将当前正方形范围标记为已访问状态
                updateVisited(visited, r, c, i, 1);
                // 递归到下一层，下一层的起点从当前正方形的右上角开始向后
                helper(visited, r, c+i, count+1);
                // 为了下次循环，还原当前正方形范围的访问状态
                updateVisited(visited, r, c, i, 0);
            }
            return;
        }
        col=0;
    }
    // 程序到此说明已经铺满所有区域。
    min=Math.min(min, count);
}
// 查看正方形区域内是否存在已访问过的点
private boolean findRectangle(int[][]visited, int row, int col, int length){
    int endRow = row+length, endCol=col+length;
    for(int i=row;i<endRow;i++){
        for(int j=col;j<endCol;j++){
            if(visited[i][j]==1) return false;
        }
    }
    return true;
}
// 更新正方形内访问记录
private void updateVisited(int[][]visited, int row, int col, int length, int val){
    int endRow = row+length, endCol=col+length;
    for(int r=row;r<endRow;r++){
        for(int c=col;c<endCol;c++) visited[r][c]=val;
    }
}

本题解法执行时间为2ms。

Runtime: 2 ms, faster than 61.80% of Java online submissions for Tiling a Rectangle with the Fewest Squares.

Memory Usage: 33.7 MB, less than 100.00% of Java online submissions for Tiling a Rectangle with the Fewest Squares.

本网站文章均为原创内容，并可随意转载，但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-1240-tiling-a-rectangle-with-the-fewest-squares-解题思路分析/