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] 就是将所有书按顺序放到书架上所需的最小高度。