1105. 填充书架

迈不过友情╰ 2023-10-04 18:52 46阅读 0赞

给定一个数组 books ，其中 books\[i\] = \[thicknessi, heighti\] 表示第 i 本书的厚度和高度。你也会得到一个整数 shelfWidth 。

按顺序 将这些书摆放到总宽度为 shelfWidth 的书架上。

先选几本书放在书架上（它们的厚度之和小于等于书架的宽度 shelfWidth ），然后再建一层书架。重复这个过程，直到把所有的书都放在书架上。

需要注意的是，在上述过程的每个步骤中，摆放书的顺序与你整理好的顺序相同。

例如，如果这里有 5 本书，那么可能的一种摆放情况是：第一和第二本书放在第一层书架上，第三本书放在第二层书架上，第四和第五本书放在最后一层书架上。  
每一层所摆放的书的最大高度就是这一层书架的层高，书架整体的高度为各层高之和。

以这种方式布置书架，返回书架整体可能的最小高度。

示例 1：

输入：books = \[\[1,1\],\[2,3\],\[2,3\],\[1,1\],\[1,1\],\[1,1\],\[1,2\]\], shelf\_width = 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  
通过次数6,223提交次数10,923

来源：力扣（LeetCode）  
链接：https://leetcode.cn/problems/filling-bookcase-shelves  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路：  
动态规划，用 dp\[i\] 表示放置前 i 本书所需要的书架最小高度，初始值 dp\[0\] = 0，其他为最大值 1000\*1000。遍历每一本书，把当前这本书作为书架最后一层的最后一本书，将这本书之前的书向后调整，看看是否可以减少之前的书架高度。状态转移方程为 dp\[i\] = min(dp\[i\] , dp\[j - 1\] + h)，其中 j 表示最后一层所能容下书籍的索引，h 表示最后一层最大高度。

图解：

样例输入：books = \[\[1,1\],\[2,3\],\[2,3\],\[1,1\],\[1,1\],\[1,1\],\[1,2\]\], shelf\_width = 4  
最后求 dp\[7\]，省略了遍历步骤，直接给出结果。

作者：smoon1989  
链接：https://leetcode.cn/problems/filling-bookcase-shelves/solution/dong-tai-gui-hua-python3-by-smoon1989/  
来源：力扣（LeetCode）  
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

class Solution:
        def minHeightShelves(self, books: List[List[int]], shelf_width: int) -> int:
            n = len(books)
            dp = [1000000] * (n + 1)
            dp[0] = 0
            for i in range(1, n + 1):
                tmp_width, j, h = 0, i, 0
                while j > 0:
                    tmp_width += books[j - 1][0]
                    if tmp_width > shelf_width:
                        break
                    h = max(h, books[j - 1][1])
                    dp[i] = min(dp[i], dp[j - 1] + h)
                    j -= 1
            return dp[-1]
    
    作者：smoon1989
    链接：https://leetcode.cn/problems/filling-bookcase-shelves/solution/dong-tai-gui-hua-python3-by-smoon1989/
    来源：力扣（LeetCode）
    著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

记第 ii 本书的高度为 h\_ih  
i  
  
，宽度为 w\_iw  
i  
  
，当第 ii 本书排在书架某一层第一个位置的时候，第 ii 本到最后一本书形成的最小高度为 dp\_idp  
i

思路的含义非常简单，就是不断的把第 ii 本书后面的书拿到和 ii 本书同层的位置（如果这一层放的下的话），计算这种情况下 dp\_idp  
i  
  
形成的高度。

作者：ivan\_allen  
链接：https://leetcode.cn/problems/filling-bookcase-shelves/solution/1105-tian-chong-shu-jia-dong-tai-gui-hua-by-ivan\_a/  
来源：力扣（LeetCode）  
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

int minHeightShelves(vector<vector<int>>& books, int shelf_width) {
        vector<int> dp(books.size() + 1, INT_MAX);
        dp[books.size()] = 0;
        for (int i = books.size() - 1; i >= 0; --i) {
            int max_book_height = 0;
            int left_width = shelf_width;
            // 把第 j 本书拿到第 i 本书后面
            for (int j = i; j < books.size() && left_width >= books[j][0]; ++j) {
                max_book_height = max(max_book_height, books[j][1]);
                dp[i] = min(dp[i], max_book_height + dp[j+1]);
                left_width -= books[j][0];
            }
        }
        return dp[0];
    }
    
    作者：ivan_allen
    链接：https://leetcode.cn/problems/filling-bookcase-shelves/solution/1105-tian-chong-shu-jia-dong-tai-gui-hua-by-ivan_a/
    来源：力扣（LeetCode）
    著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。