LeetCode 1105. 填充书架
题目描述
给定一个数组 books，其中 books[i] = [thicknessi, heighti] 表示第 i 本书的厚度和高度。你也会得到一个整数 shelfWidth，表示书架的总宽度。
按顺序将这些书摆放到总宽度为 shelfWidth 的书架上。你可以先选择几本书放在书架上（它们的厚度之和小于等于书架的宽度 shelfWidth），然后再建立一层书架。重复这个过程，直到把所有的书都放在书架上。
需要注意的是，在上述过程的每个步骤中，摆放书的顺序与给定图书数组 books 顺序相同。
每一层所摆放的书的最大高度就是这一层书架的层高，书架整体的高度为各层高之和。
要求： 返回书架整体可能的最小高度。
示例
示例 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
思路
本题是一个典型的动态规划问题。我们需要通过选择合适的方式将书本摆放到书架上，目标是最小化书架的总高度。
解题步骤：
-
定义状态：
设dp[i]表示将前i本书放入书架所需的最小总高度。 -
状态转移：
- 对于每一层书架，我们尝试放置从第
j本书到第i本书（1 ≤ j ≤ i），并保证放置的书的总厚度不超过shelfWidth。 - 设定一个变量
width用于记录当前层书架的宽度，height用于记录当前层书架的高度。对于每一层书架，我们从第j本书开始，依次加入书本，直到总厚度超过shelfWidth。 - 当我们添加新的书本时，更新当前层书架的最大高度，并将该层书架的高度加到
dp[j-1]上，更新dp[i]。
- 对于每一层书架，我们尝试放置从第
-
最终结果：
最终的结果存储在dp[n]，其中n是书本的总数，表示所有书本都放入书架所需的最小总高度。
代码实现：
def minHeightShelves(books, shelfWidth):n = len(books)dp = [float('inf')] * (n + 1) # dp[i]表示前i本书的最小高度dp[0] = 0 # 没有书时，书架的高度为0# 遍历每一本书for i in range(1, n + 1):width = 0 # 当前书架的宽度height = 0 # 当前书架的高度# 尝试从第j本书到第i本书放在同一层for j in range(i, 0, -1):width += books[j - 1][0] # 加上当前书的厚度if width > shelfWidth: # 如果宽度超过了书架的最大宽度，跳出breakheight = max(height, books[j - 1][1]) # 更新当前层书架的最大高度dp[i] = min(dp[i], dp[j - 1] + height) # 更新最小高度return dp[n]
解释：
-
初始化：
dp[0] = 0，表示没有书时，书架的高度为 0。- 其他
dp[i]初始值设置为无穷大，表示初始时无法计算的状态。
-
状态转移：
- 对于每一本书，从当前位置
i向前遍历每个可能的起点j，计算从第j本书到第i本书放在同一层书架上的最小高度。 width累加每一本书的厚度，如果超过shelfWidth则跳出。height记录当前层书架的最大高度。- 更新
dp[i]，即当前放书方式的最小总高度。
- 对于每一本书，从当前位置
-
结果：
最终，dp[n]就是将所有书按顺序放到书架上所需的最小高度。
时间复杂度
- 外层循环遍历每本书
i，内层循环遍历可能的起始位置j。每次计算时，时间复杂度为 O(n)，所以总体时间复杂度是 O(n^2)。
总结
本题的关键在于动态规划的设计，如何利用 dp[i] 记录前 i 本书的最小高度，并通过状态转移更新最优解。通过不断尝试不同的层数和放置方式，可以得到最小的书架高度。