题目分析

这是第219场周赛的第四题，是一个我们有点面熟的题目了，但是难度要比之前的大得多。

动态规划

我们拿到这个题目时，有些束手无策。但是我们发下满足条件的子序列中，一定满足一个规律。将长方体都摆成width < length < height的形状，依然是满足条件的。证明如下：

不妨设最底下长方体width，length和height分别记为a0, b0, c0，且有

$$ a \le b \le c $$

而上面的长方体记为d, e, f，d、e、f的相对关系不确定。那么有

$$ d \le a, e \le b, f \le c $$

这里将d，e，f按照从小到大排序得到m，n，p，一定有

$$ m \le a, n \le b, p \le c $$

这个逻辑小伙伴们可以进行证明。

如果f对应的值就是排序后的p，因为f小于等于c，所以p小于等于c
- 如果e对应的值就是排序后的n，因为e小于等于b，所以n小于等于b，剩下的d对应排序后的m，因为d小于等于a，所以m小于等于a
- 如果e对应的值就是排序后的m，则d对应排序后的n。因为m小于等于n，所以e小于等于d。而且已知d小于等于a，a小于等于b，所以m小于等于a，n小于等于b
如果f对应的值是排序后的n
- 如果e对应的是排序后的p，因为n小于等于p，所以f小于等于e。而且已知e小于等于b，b小于等于c，所以p小于等于c，n小于等于b。剩下的d对应排序后的m，因为d小于等于a，所以m小于等于a
- 如果e对应的是排序后的m，则d对应的是排序后的p，因为p是排序后的最大值，且d小于等于a。而且已知a小于等于b，b小于等于c，所以m一定小于等于a，n一定小于等于b
如果f对应的是排序后的m，其实结论和f对应排序后的n一样，小伙伴们可以自行推导。

因此我们将所有的长方体都按照该形状进行排列，不会影响最终结果。排列后，我们对整体进行排列，让width小的放在前面，width相同的将length小的放在前面，width和length都相同则将height小的放在前面。这样排序的目的是，让后面的长方体一定不能放在前面的长方体之上。

然后类似动态规划寻找最长递增子序列一样，满足width，length，height都大于之前的长方体才可以放入。

算法的时间复杂度为$O(n^2)$，空间复杂度为$O(n)$。

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

class Solution {
public:
    int maxHeight(vector<vector<int>>& cuboids) {
        for (auto& v : cuboids) {
            sort(v.begin(), v.end());
        }
        sort(cuboids.begin(), cuboids.end());
        vector<int> dp(cuboids.size());
        for (int i = 0; i < cuboids.size(); i++) {
            for (int j = 0; j < i; j++) {
                if (cuboids[i][1] >= cuboids[j][1] && cuboids[i][2] >= cuboids[j][2]) {
                    dp[i] = max(dp[i], dp[j]);
                }
            }
            dp[i] += cuboids[i][2];
        }
        return *max_element(dp.begin(), dp.end());
    }
};

刷题总结

这个题目我没有做出来，我想到了第一步的内部排序，排完序后，我就不知道怎么进行下面的操作了。学习了这个方法之后，我在Leetcode354题俄罗斯套娃信封问题上，发现也是可以通过的。只不过这个方法不是那个题目的最优解。因此对于多维问题，都是可以使用这个方案的，希望小伙伴们能灵活运用。