题目描述：
给出数组 books，其中 books[i] = {w,h}表示书的厚度和高度。给出一个整数 shelfWidth，表示书架的宽度。按顺序将所有的书放在书架上。如果放不下则放下一层，直到所有的书全放完，返回书架的最低高度。
数据范围：$1\le n \le 1000$
题解：
使用 $dp[i]$ 表示 $i$ 作为该层的最后一本书。那么需要考虑 $[j, i]$ 作为单独的一层。
可以倒着枚举 $j$，方便取 $sum$，直到 $sum > shelfWidth$ 时退出。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
| auto optimize_cpp_stdio = []()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
return 0;
}();
class Solution
{
public:
const static int maxn = 1e3 + 10;
int dp[maxn];
int minHeightShelves(vector<vector<int>> &books, int shelfWidth)
{
int n = books.size();
dp[0] = 0;
for (int i = 1; i <= n; ++i)
{
dp[i] = dp[i - 1] + books[i - 1][1];
int sum_w = books[i - 1][0];
int max_h = books[i - 1][1];
for (int j = i - 1; j > 0; --j)
{
sum_w += books[j - 1][0];
if (sum_w > shelfWidth)
break;
max_h = max(max_h, books[j - 1][1]);
dp[i] = min(dp[i], dp[j - 1] + max_h);
}
}
return dp[n];
}
};
|