糖逗 发表于 2022-5-22 16:07:18

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]
查看完整版本: C++刷LeetCode(面试题 08.13. 堆箱子)【动态规划】*