每日一题：堆箱子

赞

题目：堆箱子

堆箱子。给你一堆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
提示:

  1. 箱子的数目不大于3000个。

分析

这题在回溯类型下，但无奈用回溯方法会超时，剪枝太麻烦，就使用了动态规划方法，首先选择 一个维度对输入box排序，用dp保存当前节点在底部的最大高度，见代码

代码

class Solution {public:    int pileBox(vector<vector<int>>& box) {        // 首先对输入box选择一个维度排序        std::sort(box.begin(), box.end(), [](const vector<int> &a, const vector<int> &b) {            return a[0] < b[0];        });        int size = box.size();        vector<int> dp(size, 0); // dp保存当前节点在底部的最大高度        dp[0] = box[0][2];        int ret = dp[0];        for (int i = 1; i < size; ++i) {            int max_val = 0;            for (int j = 0; j < i; ++j) {                if (IsValid(box[j], box[i])) {                    max_val = max(max_val, dp[j]);                }            }            dp[i] = max_val + box[i][2];            ret = max(ret, dp[i]);        }        return ret;    }

    bool IsValid(vector<int> &up, vector<int> &down) {        return (down.at(0) > up.at(0)                && down.at(1) > up.at(1)                && down.at(2) > up.at(2));    }};