https://leetcode.cn/problems/maximum-height-by-stacking-cuboids/description/
给你 n 个长方体 cuboids ，其中第 i 个长方体的长宽高表示为 cuboids[i] = [widthi, lengthi, heighti]（下标从 0 开始）。
请你从 cuboids 选出一个 子集 ，并将它们堆叠起来。
如果 widthi <= widthj 且 lengthi <= lengthj 且 heighti <= heightj ，你就可以将长方体 i 堆叠在长方体 j 上。
你可以通过旋转把长方体的长宽高重新排列，以将它放在另一个长方体上。
返回 堆叠长方体 cuboids 可以得到的 最大高度 。
示例 1：
输入：cuboids = [[50,45,20],[95,37,53],[45,23,12]]
输出：190
解释：
第 1 个长方体放在底部，53x37 的一面朝下，高度为 95 。
第 0 个长方体放在中间，45x20 的一面朝下，高度为 50 。
第 2 个长方体放在上面，23x12 的一面朝下，高度为 45 。
总高度是 95 + 50 + 45 = 190 。
示例 2：
输入：cuboids = [[38,25,45],[76,35,3]]
输出：76
解释：
无法将任何长方体放在另一个上面。
选择第 1 个长方体然后旋转它，使 35x3 的一面朝下，其高度为 76 。
示例 3：
输入：cuboids = [[7,11,17],[7,17,11],[11,7,17],[11,17,7],[17,7,11],[17,11,7]]
输出：102
解释：
重新排列长方体后，可以看到所有长方体的尺寸都相同。
你可以把 11x7 的一面朝下，这样它们的高度就是 17 。
堆叠长方体的最大高度为 6 * 17 = 102 。
提示：
n == cuboids.length
1 <= n <= 100
1 <= widthi, lengthi, heighti <= 100
根据题目的数据范围
我们将每个长方体的可能的长宽高组合都考虑进去，那么每个长方体有6个组合(123,132,213,231,312,321)，制作一个新的数据队列进行01背包动态规划，
保证不多次选择同一个长方体也是能够通过的。复杂度是O(n^2),只是n扩大了6倍。
我们这里考虑优化计算方式.
1 将每个长方体的三个维度进行从小到大排序
2 按照排序后的长方体按照三个维度关键字进行排序。
3 进行dp，寻找符合条件的最长上升子序列（排序中，长方体最大的那个维度作为高来使用）
这种做法需要证明两个问题：
1 为什么每个长方体的三个维度进行排序，再按照三个维度关键字进行排序，就保证正确答案在里面。
也就是长方体{1,2,3}能堆叠在长方体{4,5,6}, {2,3,1}能堆叠在{6,4,5}上 是相同。
{4,5,3}能堆叠在(5,3,7}上和 {3,4,5}能堆叠在{3,5,7}上是相同的。
设两个长方体,A={a1,a2,a3},B={b1,b2,b3} ,并且a1<=a2<=a3, b1<=b2<=b3
A能堆叠在B上，要求证明当且仅当a1<=b1 ,a2<=b2,a3<=b3
1 a1<=b1 ,a2<=b2,a3<=b3 推导出===> A能堆叠在B上 这是题目的定义
2 A能堆叠在B上 推导出==> a1<=b1,a2<=b2,a3<=b3
因为已有a1<=a2<=a3, b1<=b2<=b3，A能堆叠在B上，那么一定有 最小的a1<=b1,最大的 b3>=(a1,a2,a3) 也就是a3<=b3,否则A不可能堆叠在B上
同样的a2不可能>B3,如果a2>B2,那么A不可能堆叠在B上。所以a2<=b2.
2 为什么长方体排序后，使用最大的维度作为高度，就得到 堆叠长方体的最大高度。
这是因为我们在求最长递增子序列，在确定了子序列的最长长度，使用维度最高的边作为高度，那么他们的高度和就是最大高度。
假设有其他更高的不全部使用最长维度作为高度的选择组合，这个选择组合的长度需要比最长上升序列的长度至少要大一。
但是不存在比最长上升序列更长的上升序列。 所以把最长的边作为高是最优的。
两个问题解决后，代码如下
class Solution {
public:
int maxHeight(vector<vector<int>>& cuboids) {
//长方体的维度排序和长方体的三维度排序
for (auto& e : cuboids) {
sort(e.begin(), e.end());
}
sort(cuboids.begin(),cuboids.end());
//插入一个元素，dp可以从1 开始 避免边界问题
cuboids.insert(cuboids.begin(), vector<int>{0,0,0});
int dp[105]; memset(dp,-0x3f,sizeof dp);
dp[0] = 0;
//dp[i] 等于以第i个长方体结尾的最大高度
for (int i = 1; i < cuboids.size(); i++) {
for (int j = 0; j < i;j++) {
if (cuboids[i][0] >= cuboids[j][0] && cuboids[i][1] >= cuboids[j][1] && cuboids[i][2] >= cuboids[j][2]) {
dp[i] = max(dp[i], dp[j] + cuboids[i][2]);
}
}
}
//得到以任意长方体结尾的最大高度中的最大值
int ans = 0;
for (int i = 0; i < cuboids.size(); i++) {
ans = max(ans, dp[i]);
}
return ans;
}
};