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

题目大意:

铺瓷砖

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

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

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

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

示例 1:

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

示例 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-解题思路分析/
此条目发表在leetcode分类目录,贴了, , 标签。将固定链接加入收藏夹。

发表评论

您的电子邮箱地址不会被公开。