1691.堆叠长方体的最大高度

链接：1691.堆叠长方体的最大高度
难度：Hard
标签：数组、动态规划、排序
简介：返回 堆叠长方体 cuboids 可以得到的 最大高度 。

题解 1 - cpp

• 编辑时间：2022-12-10
• 执行用时：12ms
• 内存消耗：8.9MB
• 编程语言：cpp
• 解法介绍：dp[i]表示 i 作为最后一个点的时候的最大高度。

class Solution {
public:
    int maxHeight(vector<vector<int>>& cuboids) {
        int n = cuboids.size(), ans = 0;
        vector<int> dp(n);
        sort(cuboids.begin(), cuboids.end(), [](const vector<int> &a, const vector<int> &b){
            return a[0] + a[1] + a[2] > b[0] + b[1] + b[2];
        });
        for (auto &item : cuboids) sort(item.begin(), item.end());
        for (int i = 0; i < n; i++) {
            dp[i] = cuboids[i][2];
            for (int j = 0; j < i; j++) {
                if (cuboids[j][0] < cuboids[i][0] || cuboids[j][1] < cuboids[i][1] || cuboids[j][2] < cuboids[i][2]) continue;
                dp[i] = max(dp[i], dp[j] + cuboids[i][2]);
            }
            ans = max(ans, dp[i]);
        }
        return ans;
    }
};