文章目錄

• • 1. 題目
  • 2. 解題

1. 題目

附近的家居城促銷，你買回了一直心儀的可調(diào)節(jié)書架，打算把自己的書都整理到新的書架上。

你把要擺放的書 books 都整理好，疊成一摞：從上往下，第 i 本書的厚度為 books[i][0]，高度為 books[i][1]。

按順序 將這些書擺放到總寬度為 shelf_width 的書架上。

先選幾本書放在書架上（它們的厚度之和小于等于書架的寬度 shelf_width），然后再建一層書架。重復(fù)這個(gè)過程，直到把所有的書都放在書架上。

需要注意的是，在上述過程的每個(gè)步驟中，擺放書的順序與你整理好的順序相同。
例如，如果這里有 5 本書，那么可能的一種擺放情況是：第一和第二本書放在第一層書架上，第三本書放在第二層書架上，第四和第五本書放在最后一層書架上。

每一層所擺放的書的最大高度就是這一層書架的層高，書架整體的高度為各層高之和。

以這種方式布置書架，返回書架整體可能的最小高度。

示例：

輸入：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 本書不必放在第一層書架上。提示： 1 <= books.length <= 1000 1 <= books[i][0] <= shelf_width <= 1000 1 <= books[i][1] <= 1000

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/filling-bookcase-shelves
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處。

2. 解題

• 注意題目說必須按照順序擺放
• dp[i] 表示 i 書籍在該層的最右邊時(shí)，書架的最小高度

class Solution { public:int minHeightShelves(vector<vector<int>>& books, int shelf_width) {int n = books.size();vector<int> dp(n+1, INT_MAX);dp[0] = 0;//沒有書的時(shí)候for(int i = 1; i <= n; ++i){int w = 0, h = 0;for(int j = i; j > 0; --j){if(w+books[j-1][0] <= shelf_width){ // 這一層還能放前面的書h = max(h, books[j-1][1]);//這層的高度w += books[j-1][0];//這層的寬度dp[i] = min(dp[j-1]+h, dp[i]);// 上一層的最右側(cè)是 j-1 書籍，最低書架高度是 dp[j-1]// 加上當(dāng)前層的高度 h }elsebreak;}}return dp[n];} };

4 ms 7.6 MB C++

---

我的CSDN博客地址 https://michael.blog.csdn.net/

長按或掃碼關(guān)注我的公眾號（Michael阿明），一起加油、一起學(xué)習(xí)進(jìn)步！

總結(jié)

以上是生活随笔為你收集整理的LeetCode 1105. 填充书架（DP）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。