LeetCode 1105. 填充书架

2023-05-07 HGNULB 约 6 分钟

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

分类

题目描述

✅ 1105. 填充书架

题意分析

一排书按给定顺序摆上书架，书架每层有固定的宽度上限 shelfWidth。可以在任意位置换到下一层，但不能调换书的先后顺序。某一层的高度等于该层最高那本书的高度，书架总高度是各层高度之和。求最小总高度。

有三个约束必须先读准。第一，顺序固定——这把问题从「任意分组」压成了「把一个序列切成若干连续段」，这是本题最重要的结构信息，也是后面能用一维状态描述问题的根本原因。第二，每层的代价是段内最大值而不是求和，代价随段变长只增不减但增幅不确定。第三，宽度是硬约束，段内宽度和不能超过 shelfWidth。

这三条组合起来给出一个反直觉的现象：贪心地把每层塞满是错的。把一本很高的书硬塞进当前层，会让这一层的高度被它拉满；而把它留到下一层，可能与另一本同样高的书共用高度，总高反而更小。局部最优不等于全局最优，所以必须考虑所有切分方式。

约束里 books.length 上限 1000。$n^2 = 10^6$ 完全可以接受，这个规模明确允许「枚举每个可能的最后一段」这种平方级做法，不必去追求更优的单调队列优化。

边界：只有一本书时答案就是它的高度；单本书的宽度题目保证不超过 shelfWidth，所以一定有可行解，不存在无解情况。

解法：动态规划状态转移

核心思路

书的顺序不能改变，因此每层书必然是原数组的一段连续区间，问题等价于：把数组切成若干合法连续段，使每段最大高度之和最小。这是典型的线性划分动态规划。

定义 dp[i] 为摆完前 i 本书（下标 0..i-1）的最小总高度，dp[0] = 0。若最后一层从下标 j 放到 i-1，则
\[dp[i]=\min_{0\le j<i}\left(dp[j]+\max_{j\le k<i}height_k\right)\]
其中只枚举满足 $\sum_{k=j}^{i-1}thickness_k\le shelfWidth$ 的 j。

为什么这样转移完整且正确？任取一个摆放前 i 本书的最优方案，它的最后一层一定存在唯一的起点 j。最后一层之前是前 j 本书；若那部分不是 dp[j] 所代表的最优方案，就能替换成更优前缀并降低总高度，与整体最优矛盾。因此每个最优方案都被某个候选覆盖。反过来，每个候选都由一个合法的最优前缀和一层宽度不超限的新书架组成，所以一定可行。两边合起来证明了转移式。

枚举 j 时从右向左扩展最后一层，并同步维护累计宽度与最大高度，每个候选只需 $O(1)$ 更新。宽度一旦超限，再向左只会更宽，可以立即停止。

不能贪心地把当前层尽量塞满。反例 books = [[1,1],[2,3],[2,3],[1,1]]、shelfWidth = 4：塞满得到两层高度 3+3=6；最优切分是 [1,1] / [[2,3],[2,3]] / [1,1]，总高度 1+3+1=5。

解题步骤

建立长度为 n + 1 的数组，令 dp[0] = 0。

按 i = 1..n 计算状态。先让第 i 本书单独占最后一层，得到必定合法的初值 dp[i] = dp[i-1] + books[i-1][1]，无需无穷大哨兵。

令 width、height 分别为当前最后一层的总宽度和最大高度，从 j = i-2 向左加入书。

每加入一本先累加宽度；若超过 shelfWidth 就停止。否则更新层高，并用 dp[j] + height 更新 dp[i]。

返回 dp[n]。

以 books = [[1,3],[2,4],[3,2]]、shelfWidth = 4 为例：dp[1]=3；前两本同层时宽 3、高 4，所以 dp[2]=4；计算 dp[3] 时，第三本单独放得到 dp[2]+2=6，再加入第二本会宽 5 超限，因此答案为 6。

代码实现

class Solution {
    public int minHeightShelves(int[][] books, int shelfWidth) {
        int n = books.length;
        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]);
                dp[i] = Math.min(dp[i], dp[j] + height);
            }
        }
        return dp[n];
    }
}

func minHeightShelves(books [][]int, shelfWidth int) int {
	n := len(books)
	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]
			}
			if dp[j]+height < dp[i] {
				dp[i] = dp[j] + height
			}
		}
	}
	return dp[n]
}

复杂度分析

时间复杂度：$O(n^2)$。每个右端点最多向左枚举 $n$ 个起点，每次只做常数次更新；提前停止不改变最坏界。

空间复杂度：$O(n)$，用于一维 dp 数组。

关键点总结

顺序固定意味着每层是连续段，状态应落在前缀边界上。

dp[i] 只描述前 i 本书的最优高度；最后一层的起点 j 连接了子问题与当前决策。

正确性的核心是最优子结构：最优方案删掉最后一层后，剩余前缀也必须最优。

从右向左扩展最后一层，可同时增量维护宽度和最大高度；宽度超限后可以安全停止。

单本书必定不超宽，用“最后一本单独成层”初始化比使用无穷大哨兵更简单、也没有溢出风险。

易错点总结

贪心塞满当前层不正确。上述四本书反例中，贪心得 6，主动提前换层才能得到 5。

把层高写成高度之和。[[1,3],[2,4]] 在同层时高度是 4，不是 7。

状态下标混淆：当最后一层是 books[j..i-1] 时，前缀恰好有 j 本，应连接 dp[j]，不是 dp[j-1]。

宽度超限后仍更新答案会引入非法方案；必须先判断 width > shelfWidth。

只有从右向左扩展时，累计宽度才随循环单调增加并允许 break。改成从左向右枚举起点后照搬 break 会漏掉后面的合法短区间。

每个候选都重新扫描区间求宽高会退化到 $O(n^3)$；宽度和最大高度应随 j 增量维护。

相似题目

题目	难度	考察点
1043. 分隔数组以得到最大和	中等	同为枚举最后一段的划分 DP，但段长有上限、段价值是 `max × 段长`
813. 最大平均值和的分组	中等	段数固定为 `k`，状态要多一维记录已用段数，段价值改为平均值
132. 分割回文串 II	困难	段的合法性由回文判定给出，需先预处理回文表再做同样的最后一段枚举
139. 单词拆分	中等	划分 DP 的判定版，`dp[i]` 是布尔值，转移条件换成字典命中
410. 分割数组的最大值	困难	目标是最小化各段和的最大值，除划分 DP 外还可二分答案 + 贪心检验
91. 解码方法	中等	最简单的划分 DP，最后一段长度只能是 1 或 2，练习状态与转移的对应