LeetCode 1240. 铺瓷砖

Categories:

题目描述
思路分析
1. 解法一：回溯 + 剪枝（推荐）
相似题目

题目描述

✅ 1240. 铺瓷砖

思路分析

解法一：回溯 + 剪枝（推荐）

核心思路：

使用高度数组表示当前每列已铺高度，寻找最低位置填充。

尝试从大到小放置正方形，减少搜索深度。

结合剪枝（当前已用块数 >= 最优解）避免无效搜索。

复杂度分析：

时间复杂度：O(k)，实际由搜索树决定。

空间复杂度：O(n)，递归栈与高度数组。

import java.util.Arrays;

class Solution {
    private int best;
    private int n;
    private int m;

    public int tilingRectangle(int n, int m) {
        this.n = n;
        this.m = m;
        this.best = n * m;

        int[] heights = new int[n];
        dfs(heights, 0);

        return best;
    }

    private void dfs(int[] heights, int used) {
        if (used >= best) {
            return;
        }

        int minH = Integer.MAX_VALUE;
        int idx = -1;
        for (int i = 0; i < n; i++) {
            if (heights[i] < minH) {
                minH = heights[i];
                idx = i;
            }
        }

        if (minH == m) {
            best = Math.min(best, used);
            return;
        }

        int maxSize = 1;
        while (idx + maxSize <= n && minH + maxSize <= m) {
            boolean ok = true;
            for (int k = idx; k < idx + maxSize; k++) {
                if (heights[k] != minH) {
                    ok = false;
                    break;
                }
            }
            if (!ok) {
                break;
            }
            maxSize++;
        }
        maxSize--;

        for (int size = maxSize; size >= 1; size--) {
            int[] next = Arrays.copyOf(heights, n);
            for (int k = idx; k < idx + size; k++) {
                next[k] += size;
            }
            dfs(next, used + 1);
        }
    }
}

func tilingRectangle(n int, m int) int {
	best := n * m
	heights := make([]int, n)

	var dfs func([]int, int)
	dfs = func(h []int, used int) {
		if used >= best {
			return
		}

		minH := 1 << 30
		idx := -1
		for i := 0; i < n; i++ {
			if h[i] < minH {
				minH = h[i]
				idx = i
			}
		}
		if minH == m {
			if used < best {
				best = used
			}
			return
		}

		maxSize := 1
		for idx+maxSize <= n && minH+maxSize <= m {
			ok := true
			for k := idx; k < idx+maxSize; k++ {
				if h[k] != minH {
					ok = false
					break
				}
			}
			if !ok {
				break
			}
			maxSize++
		}
		maxSize--

		for size := maxSize; size >= 1; size-- {
			next := make([]int, n)
			copy(next, h)
			for k := idx; k < idx+size; k++ {
				next[k] += size
			}
			dfs(next, used+1)
		}
	}

	dfs(heights, 0)
	return best
}

相似题目

题目	难度	考察点
1240. 铺瓷砖	困难	回溯、剪枝
312. 戳气球	困难	DP
699. 掉落的方块	困难	区间处理
698. 划分为 k 个相等的子集	中等	回溯
79. 单词搜索	中等	回溯

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2022/58546309