堆箱子
- 难度：Hard
- 题目链接：https://leetcode-cn.com/problems/pile-box-lcci/
题目描述
堆箱子。给你一堆n个箱子，箱子宽 wi、深 di、高 hi。箱子不能翻转，将箱子堆起来时，下面箱子的宽度、高度和深度必须大于上面的箱子。实现一种方法，搭出最高的一堆箱子。箱堆的高度为每个箱子高度的总和。
输入使用数组[wi, di, hi]表示每个箱子。
示例1:
输入：box = [[1, 1, 1], [2, 2, 2], [3, 3, 3]] 输出：6
示例2:
输入：box = [[1, 1, 1], [2, 3, 4], [2, 6, 7], [3, 4, 5]] 输出：10
提示:
- 箱子的数目不大于3000个。
解法：
先想出暴力解法，即以每个箱子为最底下的箱子。然后在余下的箱子中寻找下一个箱子，下一个箱子自然是比前一个要小的，而后再寻找更小的。这就是一个 dfs 的过程。
选择一个箱子作为作为底之后，可以把问题转换为在约束条件下，求其余箱子能叠出的最大高度。可以把子问题的解（以每个箱子为底所能得到的最大高度）缓存下来，以加速计算。
另外，可以在维度上进行升序排列，这样当前箱子后面的所有箱子都不可能处于该箱子之上。
class Solution {
public:
int pileBox(vector<vector<int>>& box) {
sort(box.begin(), box.end(), [](auto& a, auto& b){
return a[0] < b[0];
});
vector<int> cache(box.size(), -1);
int max_height = 0;
for(int i = 0; i < box.size(); i++){
max_height = max(max_height, dfs(box, i, cache));
}
return max_height;
}
int dfs(vector<vector<int>>& box, int bottom_box_i, vector<int>& cache){
if(cache[bottom_box_i] != -1){
return cache[bottom_box_i];
}
int ret = 0;
vector<int> &bottom_box = box[bottom_box_i];
for(int i = 0; i < bottom_box_i; i++){
if(small(box[i], bottom_box)){
ret = max(ret, dfs(box, i, cache));
}
}
ret = ret + bottom_box[2];
cache[bottom_box_i] = ret;
return ret;
}
bool small(const vector<int> &box1, const vector<int> &box2){
for(int i = 0;i<box1.size();i++){
if(box1[i] >= box2[i]){
return false;
}
}
return true;
}
};
改写成动态规划如下：
class Solution {
public:
int pileBox(vector<vector<int>>& box) {
sort(box.begin(), box.end(), [](auto& a, auto& b){
return a[0] < b[0];
});
vector<int> dp(box.size(), 0);
dp[0] = box[0][2];
int ret = dp[0];
for(int i = 1; i < box.size(); i++){
int max_height = 0;
for(int j = 0; j < i; j++){
if(small(box[j], box[i])){
max_height = max(max_height, dp[j]);
}
}
dp[i] = max_height + box[i][2];
ret = max(ret, dp[i]);
}
return ret;
}
bool small(const vector<int> &box1, const vector<int> &box2){
for(int i = 0;i<box1.size();i++){
if(box1[i] >= box2[i]){
return false;
}
}
return true;
}
};