比较好的高端网站制作公司,wordpress怎么禁止评论,直接找高校研究生做网站行吗,网站建设费汇算清缴1. 题目
堆箱子。给你一堆n个箱子#xff0c;箱子宽 wi、深 di、高 hi。 箱子不能翻转#xff0c;将箱子堆起来时#xff0c;下面箱子的宽度、高度和深度必须大于上面的箱子。 实现一种方法#xff0c;搭出最高的一堆箱子。箱堆的高度为每个箱子高度的总和。
输入使用数组…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(vectorvectorint box) {sort(box.begin(), box.end(),[](auto a, auto b) {return a[0] b[0];//宽降序});int i, j, n box.size();vectorint 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
