上次编辑到这里，代码来自缓存 点击恢复默认模板
class Solution {
public:
int minHeightShelves(vector<vector<int>>& books, int shelfWidth) {
}
};
python3 解法, 执行用时: 32 ms, 内存消耗: 15.1 MB, 提交时间: 2022-12-08 10:27:02
'''
用 dp[i] 表示放置前 i 本书所需要的书架最小高度，初始值 dp[0] = 0，其他为最大值 1000*1000。
遍历每一本书，把当前这本书作为书架最后一层的最后一本书，将这本书之前的书向后调整，
看看是否可以减少之前的书架高度。状态转移方程为 dp[i] = min(dp[i] , dp[j - 1] + h)，
其中 j 表示最后一层所能容下书籍的索引，h 表示最后一层最大高度。
'''
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]
java 解法, 执行用时: 0 ms, 内存消耗: 40.9 MB, 提交时间: 2022-12-08 10:25:55
class Solution {
public int minHeightShelves(int[][] books, int shelf_width) {
int n = books.length;
int[] dp = new int[n + 1];
Arrays.fill(dp, Integer.MAX_VALUE);
dp[n] = 0;
// 倒着处理书本，因为数组的最后一个在整个书架的最上面
for (int i = n - 1; i >= 0; --i) {
// 首先假设这一层高度为 0
int maxHeight = 0;
// 当前层剩余的宽度为 leftWidth
int leftWidth = shelf_width;
// 根据处理到的书以及之前出现的，尝试把之前出现的书放到当前层，看看能不能达到最小值
for (int j = i; j < n && leftWidth >= books[j][0]; ++j) {
maxHeight = Math.max(maxHeight, books[j][1]);
dp[i] = Math.min(dp[i], maxHeight + dp[j + 1]);
leftWidth -= books[j][0];
}
}
return dp[0];
}
}
cpp 解法, 执行用时: 4 ms, 内存消耗: 7.8 MB, 提交时间: 2022-12-08 10:25:34
class Solution {
public:
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];
}
};
python3 解法, 执行用时: 48 ms, 内存消耗: 15.2 MB, 提交时间: 2022-12-08 10:24:11
'''
将第i本书当做最后一本书，我们需要求i本书的最小高度f[i]。
所以如果最后一本书放到新的一层中，f[i] = f[i-1] + books[i-1][1]
最后一本书也可以和他前一本书一同放到新的一层。这时：f[i] = f[i-2] + max(books[i-1][1]，books[i-2][1])
'''
class Solution:
def minHeightShelves(self, books: List[List[int]], shelf_width: int) -> int:
import sys
n = len(books)
f = [sys.maxsize]*(n+1)
f[0] = 0
for i in range(1,n+1):
cur_height = 0 #以第i本书作为最后一本书，最后一层的高度
cur_weight = 0 #以第i本书作为最后一本书，最后一层的宽度
for j in range(i,0,-1):
cur_height = max(cur_height,books[j-1][1])
cur_weight += books[j-1][0]
if(cur_weight>shelf_width):
break
f[i] = min(f[i],f[j-1] + cur_height)
return f[-1]
