C++刷LeetCode（面试题 08.13. 堆箱子）【动态规划】*

糖逗

题目描述：

堆箱子。给你一堆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/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[0] < b[0];
        });
        //初始化
        vector<int>dp(n, 0);
        dp[0] = box[0][2];
        int res = dp[0];
        //动态规划dp[i]表示最后一个为i的maxhi
        for(int i = 1; i < n; i++){
            dp[i] = box[i][2];//初始至少为自己的高度
            for(int 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], dp[j] + box[i][2]);
                }
            }
            res = max(res, dp[i]);
        }
        return res;
    }
};