leetcode原题：堆箱子（动态规划实现）-Toy模板网

这篇具有很好参考价值的文章主要介绍了leetcode原题：堆箱子（动态规划实现）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

题目：

给你一堆n个箱子，箱子宽 wi、深 di、高 hi。箱子不能翻转，将箱子堆起来时，下面箱子的宽度、高度和深度必须大于上面的箱子。实现一种方法，搭出最高的一堆箱子。箱堆的高度为每个箱子高度的总和。

输入使用数组[wi, di, hi]表示每个箱子。

示例：

输入：box = [[1, 1, 1], [2, 2, 2], [3, 3, 3]]
输出：6

输入：box = [[1, 1, 1], [2, 3, 4], [2, 6, 7], [3, 4, 5]]
输出：10

解题思路：

1.先对数组进行排序，我们按照箱子的第一个值宽来进行升序排序（这里为什么不用高呢？因为尽管我们需要计算的是最大高度，但最终堆箱子需要宽、深、高都小于下面的箱子，所以直接按宽来排序）

2.用dp[i]记录以第i个箱子结尾的箱堆的最大高度

3.返回dp[n]

源代码如下：文章来源地址https://www.toymoban.com/news/detail-676143.html

class Solution {
public:
    int pileBox(vector<vector<int>>& box) {
    //先按箱子的宽wi 进行升序排序
        sort(box.begin(),box.end(),[](const vector<int>& a,const vector<int>& b){return a[0]<b[0];});
        //计算有多少个箱子
        int n=box.size();
        vector<int> dp(n,0);
        //dp[i]表示以第i个箱子结尾的最高箱子高度
        //起始的高度就是第一个箱子的高度
        dp[0]=box[0][2];
        //ans记录答案
        int ans=dp[0];
        //从第二个箱子开始找最大高度的箱子堆
        for(int i=1;i<n;i++)
        {
            //每找一次 都要讲当前最大高度置为0
            int max_hi=0;
            //找第i个箱子之前的其他箱子，组成箱子堆
            for(int j=0;j<i;j++)
            {
                //符合条件，长宽高都小于下面的箱子，才能堆到上面
                if(box[j][0]<box[i][0]&&box[j][1]<box[i][1]&&box[j][2]<box[i][2])
                {
                    //当前最大高度
                    max_hi=max(max_hi,dp[j]);
                }
                //dp[i]就等于当前最大高度+当前箱子的高度
                dp[i]=max_hi+box[i][2];
                //更新答案的最大值
                ans=max(ans,dp[i]);
            }
        }
        //返回答案
        return ans;
    }
};

到了这里，关于leetcode原题：堆箱子（动态规划实现）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！