填充書架

力扣鏈接：1105. 填充書架

題目描述

給定一個(gè)數(shù)組 books ，其中 books[i] = [thicknessi, heighti] 表示第 i 本書的厚度和高度。你也會(huì)得到一個(gè)整數(shù) shelfWidth 。

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

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

需要注意的是，在上述過程的每個(gè)步驟中，擺放書的順序與你整理好的順序相同。

例如，如果這里有 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

Java代碼

class Solution {public int minHeightShelves(int[][] books, int shelfWidth) {int[] dp = new int[books.length + 1];for (int i = 0; i < books.length; i++) {dp[i + 1] = Integer.MAX_VALUE;int width = 0, maxHeight = 0;for (int j = i; j >= 0; j--) {if (shelfWidth < (width += books[j][0])) {break;}maxHeight = Math.max(maxHeight, books[j][1]);dp[i + 1] = Math.min(dp[i + 1], dp[j] + maxHeight);}}return dp[dp.length - 1];}
}

---

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