题目
堆箱子。给你一堆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
解题
方法一：动态规划
本题可以用到leetcode-300：最长递增子序列的方法，只需要稍加处理，就可以变成最长递增子序列的题目。
由于长宽高都要是底部大于上层的。因此只需要按照任意维度，从小到大排。那么箱子从高到低的 顺序就是那个排序结果的子序列。那么就是一个递增子序列的问题。
dp[i]表示，以索引为i的箱子为底的时候，最大的高度。
class Solution { public: int pileBox(vector<vector<int>>& box) { int n=box.size(); sort(box.begin(),box.end(),[](vector<int>&a,vector<int>&b){return a[0]<b[0];}); vector<int> dp(n); int res=box[0][2]; dp[0]=box[0][2]; for(int i=1;i<n;i++){ int maxH=0;//选第i个箱子前，满足条件，且最大的堆叠高度。 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]){ maxH=max(maxH,dp[j]); } } dp[i]=maxH+box[i][2]; res=max(res,dp[i]); } return res; } };
