C++刷LeetCode(面试题 08.13. 堆箱子)【动态规划】*
题目描述:堆箱子。给你一堆n个箱子,箱子宽 wi、深 di、高 hi。箱子不能翻转,将箱子堆起来时,下面箱子的宽度、高度和深度必须大于上面的箱子。实现一种方法,搭出最高的一堆箱子。箱堆的高度为每个箱子高度的总和。
输入使用数组表示每个箱子。
示例1:
输入:box = [, , ]
输出:6
示例2:
输入:box = [, , , ]
输出:10
提示:
箱子的数目不大于3000个。
来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/pile-box-lcci
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
class Solution {
public:
int pileBox(vector<vector<int>>& box) {
int n = box.size();
sort(box.begin(), box.end(), [](const vector<int>& a, const vector<int>& b){
return a < b;
});
//初始化
vector<int>dp(n, 0);
dp = box;
int res = dp;
//动态规划dp表示最后一个为i的maxhi
for(int i = 1; i < n; i++){
dp = box;//初始至少为自己的高度
for(int j = 0; j < i; j++){
if(box > box && box > box && box > box){
dp = max(dp, dp + box);
}
}
res = max(res, dp);
}
return res;
}
};
页:
[1]