题目链接：1105. 填充书架
方法一：记忆化搜索
解题思路
- \(dfs(i)\)：从 \(i\) 到 \(n - 1\) 书放置的最小高度总和；
- 对于每一层：枚举当前层放置从 \(i\) 开始的书，放置几本时整体的高度最优，按题目要求，必须是从 \(i\) 开始的连续几本书，当前层的高度取最优方案中书的最高值；
- 返回 \(dfs(0)\)。
代码
class Solution {
public:
int minHeightShelves(vector<vector<int>>& books, int shelfWidth) {
const int n = books.size();
int cache[n]; memset(cache, -1, sizeof(cache));
function<int(int)> dfs = [&](int i) -> int {
if (i == n) return 0;
if (cache[i] != -1) return cache[i];
int &res = cache[i], width = shelfWidth, high = 0;
res = INT_MAX;
for (int j = i; j < n; j ++ ) { // 枚举
if (width < books[j][0]) break;
width -= books[j][0];
high = max(high, books[j][1]);
res = min(res, dfs(j + 1) + high); // 递归到下一层，取所有方案的最小值
}
return res;
};
return dfs(0);
}
};
复杂度分析
时间复杂度：\(O(n^2)\)；
空间复杂度：\(O(n)\)。
方法二：动态规划
解题思路
将记忆化 => 动态规划
代码
class Solution {
public:
int minHeightShelves(vector<vector<int>>& books, int shelfWidth) {
int n = books.size();
int dp[n + 1]; dp[n] = 0;
for (int i = n - 1; i >= 0; i -- ) {
int width = shelfWidth, high = 0;
dp[i] = INT_MAX;
for (int j = i; j < n; j ++ ) {
if (width < books[j][0]) break;
width -= books[j][0];
high = max(high, books[j][1]);
dp[i] = min(dp[i], dp[j + 1] + high); // 求当前层为 [i, j]，先前所有层为 [j + 1, n - 1] 为最优方案的 j
}
}
return dp[0];
}
};
复杂度分析
时间复杂度：\(O(n^2)\)；
空间复杂度：\(O(n)\)。