程序员面试金典 - 面试题 08.13. 堆箱子（DP）
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了程序员面试金典 - 面试题 08.13. 堆箱子（DP），小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1323字，纯文字阅读大概需要2分钟。
内容图文
1. 题目
堆箱子。给你一堆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个。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/pile-box-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
2. 解题
-
类似题目：
LeetCode 354. 俄罗斯套娃信封问题（最长上升子序 DP/二分查找）
程序员面试金典 - 面试题 17.08. 马戏团人塔（最长上升子序 DP/二分查找）
动态规划应用–最长递增子序列 LeetCode 300 -
对一个维度进行降序排序
-
剩下的跟最长递增子序列差不多，只不过求解的不是长度，是最大和
class Solution {
public:
int pileBox(vector<vector<int>>& box) {
sort(box.begin(), box.end(),[&](auto a, auto b) {
return a[0] > b[0];//宽降序
});
int i, j, n = box.size();
vector<int> dp(n,0);//以i箱子为顶的最大高度
for(i = 0; i < n; ++i)
{
dp[i] = box[i][2];//初始化自身高度
for(j = 0; j < i; ++j)//跟前面的比较
{
if(box[i][0] < box[j][0] && box[i][1] < box[j][1]
&& box[i][2] < box[j][2])//满足条件
{
dp[i] = max(dp[i], box[i][2]+dp[j]);//可以叠加，取最大的
}
}
}
return *max_element(dp.begin(),dp.end());
}
};
280 ms 16.7 MB
内容总结
以上是互联网集市为您收集整理的程序员面试金典 - 面试题 08.13. 堆箱子（DP）全部内容，希望文章能够帮你解决程序员面试金典 - 面试题 08.13. 堆箱子（DP）所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。