LeetCode 1105. 填充书架

2023-05-07 HGNULB 约 5 分钟

文章信息 6 个分类 · 2 个标签

分类

LeetCode CodeTop 中等 未解决 1-2 字节

标签

数组 动态规划

题目描述

✅ 1105. 填充书架

题意分析

按照输入顺序，把全部书分到若干层书架。每本书有固定厚度和高度，同一层的厚度总和不能超过 shelfWidth，这一层的高度取其中最高一本书的高度。返回所有层高度相加后的最小值。

顺序不能改变，因此每层对应输入中的一段连续书本，所有层依次覆盖整个数组。目标是总高度最小，不是层数最少，也不是每层尽量放满。题目保证每本书单独都能放进一层，所以总能构造合法方案。

解法：动态规划状态转移

核心思路

[!blue]

仅凭当前层是否还有空位，无法决定现在应该继续放书还是换层。把高书分散在不同层会重复付出较大层高，而提前换层可能让多本高书共享同一层高度。因此用动态规划枚举分层边界，而不是贪心填满每层。

定义 dp[i] 为前 i 本书能够达到的最小总高度，空前缀 dp[0] = 0。计算前 i 本时，固定最后一层的结束位置为 i - 1，枚举它从哪个下标 j 开始；最后一层就是连续区间 [j, i - 1]。

若这段书的总厚度不超宽，前面恰好剩下 j 本书，它们的最优高度为 dp[j]。整个候选高度就是 dp[j] + 当前层最大书高。前缀和最后一层之间没有剩余宽度需要共享，因此可以独立采用前缀最优方案；枚举所有合法 j 就覆盖了所有可能的最后一层。

从右向左逐本扩展最后一层，增量累加宽度并维护最大高度。厚度都为正，一旦超出 shelfWidth，再往左加书只会更宽，可以立即停止；尚未超宽时，更新层高并尝试降低 dp[i]。

初始化时先让最后一本单独成层，得到合法值 dp[i - 1] + books[i - 1][1]，再从 i - 2 开始向左扩展。这样既覆盖单本情况，也避免用默认零值参与求最小值。按前缀长度递增计算，所用的 dp[j] 都已经得到。

解题步骤

1. 创建长度为 n + 1 的状态数组，令 dp[0] = 0。
2. 计算 dp[i] 时，以最后一本书的厚度、高度作为当前层初值，并先采用它单独一层的方案。
3. 从 j = i - 2 向左加入书，先累加厚度；超宽就结束枚举。
4. 更新本层最高书高，再用 dp[j] + height 更新 dp[i]。
5. 返回前 n 本书的最优总高度 dp[n]。

代码实现

class Solution {
    public int minHeightShelves(int[][] books, int shelfWidth) {
        int n = books.length;
        // dp[i] 表示前 i 本书的最小总高度，dp[0] 对应空前缀。
        int[] dp = new int[n + 1];

        for (int i = 1; i <= n; i++) {
            int width = books[i - 1][0];
            int height = books[i - 1][1];

            // 先让最后一本单独成层，作为必定合法的初值。
            dp[i] = dp[i - 1] + height;

            for (int j = i - 2; j >= 0; j--) {
                width += books[j][0];

                // 向左扩展只会更宽，超限后可停止枚举。
                if (width > shelfWidth) {
                    break;
                }

                height = Math.max(height, books[j][1]);
                // 最后一层从 j 开始，前 j 本接 dp[j]，本层只加最高书高。
                dp[i] = Math.min(dp[i], dp[j] + height);
            }
        }

        return dp[n];
    }
}

func minHeightShelves(books [][]int, shelfWidth int) int {
    n := len(books)
    // dp[i] 表示前 i 本书的最小总高度，dp[0] 对应空前缀。
    dp := make([]int, n+1)
    for i := 1; i <= n; i++ {
        width := books[i-1][0]
        height := books[i-1][1]
        // 先让最后一本单独成层，作为必定合法的初值。
        dp[i] = dp[i-1] + height

        for j := i - 2; j >= 0; j-- {
            width += books[j][0]
            // 向左扩展只会更宽，超限后可停止枚举。
            if width > shelfWidth {
                break
            }
            if books[j][1] > height {
                height = books[j][1]
            }
            // 最后一层从 j 开始，前 j 本接 dp[j]，本层只加最高书高。
            if dp[j]+height < dp[i] {
                dp[i] = dp[j] + height
            }
        }
    }
    return dp[n]
}

复杂度分析

• 时间复杂度：$O(n^2)$，每个前缀末端最多向左枚举 n 本书，宽度和层高都以常数时间更新。
• 空间复杂度：$O(n)$，保存所有前缀的最优总高度；输入顺序不修改。

关键点总结

[!green]

• 固定顺序让每层成为连续区间，可以按最后一层切分前缀问题。
• 最后一层从 j 开始，就连接前 j 本的状态 dp[j]，不是 dp[j - 1]。
• 正厚度保证超宽后可停止，单本可放保证初始化方案合法。

易错点总结

[!yellow]

• 把同层书高相加，而不是取最大值，改变了书架层高定义。
• 为了凑宽度对书排序，破坏了必须保持输入顺序的要求。
• 超宽之后仍更新答案，会把非法的一层纳入最优值。
• 最后一层从 j 开始却接到错误的前缀下标，会遗漏或重复计算某本书。
• 用初始零值直接求 min，没有先给 dp[i] 一个合法方案，会把非空书架高度错误保留为零。
• 把当前层塞满当成最优策略，忽略了高书是否能够共享层高对总高度的影响。

相似题目

题目	难度	关联与区别
1043. 分隔数组以得到最大和	中等	同样保持顺序并枚举最后一段，原题限制段长，本题限制书宽总和并以段最大高度付费。
813. 最大平均值和的分组	中等	同样前缀分段DP，原题固定段数并按平均值计收益，本题由书架宽度决定可行分段。

转载与许可

作者 HGNULB

链接 https://hgnulb.github.io/blog/2023/35776576

许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！