1105. 填充书架
给定一个数组 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]], shelfWidth = 4
输出：6
解释：
3 层书架的高度和为 1 + 3 + 2 = 6 。
第 2 本书不必放在第一层书架上。
题解
显然dp。
对于每本书，我们有两种选择：
- 将这本书放在新的一层上；
- 将这本书放在当前层上。
状态转移方程：$dp[i] = min(dp[i], dp[j-1] + maxHeight)$
class Solution {
public:
int minHeightShelves(vector>& books, int shelfWidth) {
int n = books.size();
// 初始化动态规划数组
int dp[n+1];
dp[0] = 0;
for (int i = 1; i <= n; i++) {
// 第一种情况：将当前书放在新的一层上
dp[i] = dp[i-1] + books[i-1][1];
// 第二种情况：将书放在当前层上
int width = books[i-1][0]; // 第 i 本书的宽度
int height = books[i-1][1]; // 第 i 本书的高度
for (int j = i-1; j > 0 && width + books[j-1][0] <= shelfWidth; j--) { // 将当前书放在当前层上，从后往前尝试每一本书
height = max(height, books[j-1][1]); // 找到当前层上所有书籍的最大高度
width += books[j-1][0]; // 更新 width 的值
dp[i] = min(dp[i], dp[j-1] + height); // 计算当前状态的最小高度
}
}
return dp[n];
}
};