填充书架
难度:
标签:
题目描述
给定一个数组 books ，其中 books[i] = [thicknessi, heighti] 表示第 i 本书的厚度和高度。你也会得到一个整数 shelfWidth 。
按顺序 将这些书摆放到总宽度为 shelfWidth 的书架上。
先选几本书放在书架上（它们的厚度之和小于等于书架的宽度 shelfWidth ），然后再建一层书架。重复这个过程，直到把所有的书都放在书架上。
需要注意的是，在上述过程的每个步骤中，摆放书的顺序与给定图书数组 books 顺序相同。
- 例如，如果这里有 5 本书，那么可能的一种摆放情况是：第一和第二本书放在第一层书架上，第三本书放在第二层书架上，第四和第五本书放在最后一层书架上。
每一层所摆放的书的最大高度就是这一层书架的层高，书架整体的高度为各层高之和。
以这种方式布置书架，返回书架整体可能的最小高度。
示例 1：
输入：books = [[1,1],[2,3],[2,3],[1,1],[1,1],[1,1],[1,2]], shelfWidth = 4 输出：6 解释： 3 层书架的高度和为 1 + 3 + 2 = 6 。 第 2 本书不必放在第一层书架上。
示例 2:
输入: books = [[1,3],[2,4],[3,2]], shelfWidth = 6 输出: 4
提示：
1 <= books.length <= 10001 <= thicknessi <= shelfWidth <= 10001 <= heighti <= 1000
代码结果
运行时间: 23 ms, 内存: 16.2 MB
/*
* 思路：
* 1. 使用动态规划和Java Stream来解决这个问题。
* 2. dp数组记录每本书的最小高度。
* 3. 使用Stream对数组进行处理，找到每种可能的最小高度。
*/
import java.util.stream.IntStream;
public int minHeightShelves(int[][] books, int shelfWidth) {
int n = books.length;
int[] dp = new int[n + 1];
Arrays.fill(dp, Integer.MAX_VALUE);
dp[0] = 0;
IntStream.rangeClosed(1, n).forEach(i -> {
int[] widthHeight = {0, 0};
IntStream.iterate(i, j -> j > 0, j -> j - 1).forEach(j -> {
widthHeight[0] += books[j - 1][0];
if (widthHeight[0] > shelfWidth) return;
widthHeight[1] = Math.max(widthHeight[1], books[j - 1][1]);
dp[i] = Math.min(dp[i], dp[j - 1] + widthHeight[1]);
});
});
return dp[n];
}解释
方法:
此题解使用动态规划解决问题。定义dp数组f，其中f[i]表示放置前i本书的最小总高度。初始化f[0]为0，表示没有书时高度为0。对于每本书i，从i开始向前检查以当前书为结束的所有可能的书层配置。对每种配置，计算该层的最大高度和当前层的宽度总和。如果宽度总和没有超过书架宽度，更新f[i]为当前最优解。这样，最终f[n]中存储的就是放置所有书的最小高度。
时间复杂度:
O(n^2)
空间复杂度:
O(n)
代码细节讲解
🦆
在你的动态规划解决方案中，如何处理书的顺序？是否考虑了题目要求的‘按顺序’摆放书籍的规则？
▷🦆
动态规划数组f[i]的初始化为什么选择float('inf')，除了f[0]外，这样的初始化对算法的影响是什么？
▷🦆
在内层循环中，当书的宽度累加超过书架宽度时就会停止循环。这是否意味着我们总是在宽度超出前就不能再添加新的书？这种方式是否最优？
▷🦆
你的算法中提到更新最小高度时使用了条件判断`if f[j - 1] + mx < f[i]`。这里的逻辑是否保证了每次都能获得局部最优解，进而实现全局最优解？
▷