填充书架

标签: 数组 动态规划

难度: Medium

给定一个数组 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 <= 1000
  • 1 <= thicknessi <= shelfWidth <= 1000
  • 1 <= heighti <= 1000

Submission

运行时间: 23 ms

内存: 16.2 MB

class Solution:
    def minHeightShelves(self, books: List[List[int]], shelfWidth: int) -> int:
        n=len(books)
        f=[inf]*(n+1)
        f[0]=0
        for i in range(1,n+1):
            mx,wid=0,0
            for j in range(i,0,-1):
                if books[j-1][1]>mx: mx=books[j-1][1]
                wid+=books[j-1][0]
                if wid<=shelfWidth:
                    if f[j-1]+mx<f[i]: f[i]=f[j-1]+mx
                else:
                    break
        return f[n]

Explain

此题解使用动态规划解决问题。定义dp数组f，其中f[i]表示放置前i本书的最小总高度。初始化f[0]为0，表示没有书时高度为0。对于每本书i，从i开始向前检查以当前书为结束的所有可能的书层配置。对每种配置，计算该层的最大高度和当前层的宽度总和。如果宽度总和没有超过书架宽度，更新f[i]为当前最优解。这样，最终f[n]中存储的就是放置所有书的最小高度。

时间复杂度: O(n^2)

空间复杂度: O(n)

class Solution:
    def minHeightShelves(self, books: List[List[int]], shelfWidth: int) -> int:
        n = len(books)
        f = [float('inf')] * (n + 1)
        f[0] = 0
        for i in range(1, n + 1):
            mx, wid = 0, 0
            for j in range(i, 0, -1):
                if books[j - 1][1] > mx: mx = books[j - 1][1]  # 更新当前层的最大高度
                wid += books[j - 1][0]  # 累加当前层的宽度
                if wid <= shelfWidth:
                    if f[j - 1] + mx < f[i]: f[i] = f[j - 1] + mx  # 如果当前层宽度有效，则尝试更新最小高度
                else:
                    break
        return f[n]  # 返回放置所有书的最小总高度

Explore

在我的动态规划解决方案中，通过从前向后遍历书籍列表并逐一决定每本书的放置，来保证书籍是按照给定的顺序摆放的。内部循环从当前书籍索引i开始，并向前检查，这样可以确保书籍的顺序从1到i是连续的，符合题目要求的'按顺序'摆放规则。

在动态规划中，f[i]数组的初始化为float('inf')（意味着无穷大）用于确保在开始算法时，任何非初始状态（即f[0]除外）都不会被错误地认为是一个可行的最小值。这种初始化方式允许我们在更新每个f[i]时，只考虑那些实际上通过比较得到的更小的值。这样可以保证，每次更新f[i]都是基于有效的、可能的最小高度，而不是一个未初始化或错误初始化的值。

是的，内层循环中当书的宽度累加超过书架宽度时停止循环，确保不会添加超过书架宽度的书籍。这种设计是为了遵守书架宽度的限制，并尝试找出在不超过宽度限制的情况下的可能的最佳高度配置。虽然这种方法可能不会在每次都找到全局最优解，但它是一个有效的启发式方法，通常可以在合理的时间内找到非常接近最优的解决方案。

这个条件判断确保我们在每个步骤中都寻求局部最优解，即在给定当前书的配置下，尝试找到最小的可能高度。通过动态规划的特性，这种局部最优的决策能够累积起来，努力朝向全局最优解。虽然动态规划通常能提供全局最优解，但这也取决于问题的具体构造和状态转移的定义。在大多数情况下，本算法能有效地找到整体的最小高度。