Hard

题目描述

给定一个 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, m <= 13

提示：

  • 你能使用回溯来解决这个问题吗？
  • 假设你已经放置了一些正方形，下一个正方形的自然放置位置在哪里？
  • 放置的正方形的最大数量将是 ≤ max(n,m)。

解题思路

解题思路

这是一个经典的回溯搜索问题，需要找到用最少正方形铺满矩形的方案。

核心思路

  1. 状态表示：使用一个数组记录矩形每列的高度，表示当前已被铺满的区域
  2. 贪心策略：总是选择最左边、最低的位置放置下一个正方形
  3. 回溯搜索：对于每个位置，尝试放置不同大小的正方形，递归搜索最优解
  4. 剪枝优化：当当前使用的正方形数量已经超过目前最优解时，直接剪枝

算法流程

  • 初始化高度数组，所有位置高度为0
  • 找到当前最低的位置（优先选择最左边）
  • 在该位置尝试放置不同大小的正方形（从大到小）
  • 更新状态，递归搜索
  • 回溯时恢复状态
  • 使用剪枝优化：如果当前解已经不可能更优则提前返回

特殊情况处理

  • 如果 n == m，直接返回 1（一个正方形即可）
  • 使用记忆化或者剪枝避免重复计算

这个问题的难点在于状态空间很大，需要通过有效的剪枝来提高效率。

代码实现

class Solution {
public:
    int tilingRectangle(int n, int m) {
        vector<int> heights(m, 0);
        int result = n * m; // 最坏情况：全用1x1正方形
        backtrack(heights, n, 0, result);
        return result;
    }
    
private:
    void backtrack(vector<int>& heights, int n, int squares, int& result) {
        // 剪枝：当前方案已经不可能更优
        if (squares >= result) return;
        
        // 找到最低的位置
        int minHeight = *min_element(heights.begin(), heights.end());
        if (minHeight == n) {
            result = min(result, squares);
            return;
        }
        
        // 找到最左边的最低位置
        int pos = 0;
        while (heights[pos] != minHeight) pos++;
        
        // 尝试放置不同大小的正方形
        for (int size = min(n - minHeight, (int)heights.size() - pos); size >= 1; size--) {
            // 检查是否可以放置size x size的正方形
            bool canPlace = true;
            for (int j = pos; j < pos + size; j++) {
                if (heights[j] != minHeight) {
                    canPlace = false;
                    break;
                }
            }
            
            if (!canPlace) continue;
            
            // 放置正方形
            for (int j = pos; j < pos + size; j++) {
                heights[j] += size;
            }
            
            // 递归搜索
            backtrack(heights, n, squares + 1, result);
            
            // 回溯
            for (int j = pos; j < pos + size; j++) {
                heights[j] -= size;
            }
        }
    }
};

class Solution:
    def tilingRectangle(self, n: int, m: int) -> int:
        heights = [0] * m
        result = [n * m]  # 使用列表来允许修改
        
        def backtrack(squares):
            # 剪枝
            if squares >= result[0]:
                return
            
            # 找到最低的位置
            min_height = min(heights)
            if min_height == n:
                result[0] = min(result[0], squares)
                return
            
            # 找到最左边的最低位置
            pos = heights.index(min_height)
            
            # 尝试放置不同大小的正方形
            max_size = min(n - min_height, m - pos)
            for size in range(max_size, 0, -1):
                # 检查是否可以放置
                can_place = True
                for j in range(pos, pos + size):
                    if heights[j] != min_height:
                        can_place = False
                        break
                
                if not can_place:
                    continue
                
                # 放置正方形
                for j in range(pos, pos + size):
                    heights[j] += size
                
                # 递归搜索
                backtrack(squares + 1)
                
                # 回溯
                for j in range(pos, pos + size):
                    heights[j] -= size
        
        backtrack(0)
        return result[0]

public class Solution {
    public int TilingRectangle(int n, int m) {
        int[] heights = new int[m];
        int result = n * m; // 最坏情况
        Backtrack(heights, n, 0, ref result);
        return result;
    }
    
    private void Backtrack(int[] heights, int n, int squares, ref int result) {
        // 剪枝
        if (squares >= result) return;
        
        // 找到最低的位置
        int minHeight = heights.Min();
        if (minHeight == n) {
            result = Math.Min(result, squares);
            return;
        }
        
        // 找到最左边的最低位置
        int pos = 0;
        while (heights[pos] != minHeight) pos++;
        
        // 尝试放置不同大小的正方形
        int maxSize = Math.Min(n - minHeight, heights.Length - pos);
        for (int size = maxSize; size >= 1; size--) {
            // 检查是否可以放置
            bool canPlace = true;
            for (int j = pos; j < pos + size; j++) {
                if (heights[j] != minHeight) {
                    canPlace = false;
                    break;
                }
            }
            
            if (!canPlace) continue;
            
            // 放置正方形
            for (int j = pos; j < pos + size; j++) {
                heights[j] += size;
            }
            
            // 递归搜索
            Backtrack(heights, n, squares + 1, ref result);
            
            // 回溯
            for (int j = pos; j < pos + size; j++) {
                heights[j] -= size;
            }
        }
    }
}

var tilingRectangle = function(n, m) {
    if (n > m) [n, m] = [m, n];
    if (n === 1) return m;
    if (n === m) return 1;
    
    const memo = new Map();
    
    function dfs(state) {
        const key = state.join(',');
        if (memo.has(key)) return memo.get(key);
        
        const minHeight = Math.min(...state);
        if (minHeight === m) return 0;
        
        let pos = 0;
        while (state[pos] !== minHeight) pos++;
        
        let end = pos;
        while (end < n && state[end] === minHeight) end++;
        
        let result = Infinity;
        
        for (let size = 1; size <= Math.min(end - pos, m - minHeight); size++) {
            const newState = [...state];
            for (let i = pos; i < pos + size; i++) {
                newState[i] += size;
            }
            result = Math.min(result, 1 + dfs(newState));
        }
        
        memo.set(key, result);
        return result;
    }
    
    return dfs(new Array(n).fill(0));
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(4^(nm)) - 在最坏情况下需要探索指数级的状态空间，但通过剪枝可以显著减少实际搜索量
空间复杂度O(m + 递归深度) - 需要 O(m) 空间存储高度数组，递归深度最多为 nm

相关题目