1691. Maximum Height by Stacking Cuboids

Given n cuboids where the dimensions of the ith cuboid is cuboids[i] = [widthi, lengthi, heighti] (0-indexed). Choose a subset of cuboids and place them on each other.

You can place cuboid i on cuboid j if widthi <= widthj and lengthi <= lengthj and heighti <= heightj. You can rearrange any cuboid’s dimensions by rotating it to put it on another cuboid.

Return the maximum height of the stacked cuboids.

• Time : O(nlogn)
• Space : O(n)

c++

class Solution {
    int dp[100];
    bool bigger(vector<int> origin, vector<int> target) {
        return origin[0] >= target[0] and origin[1] >= target[1] and origin[2] >= target[2];
    }
    int solution(vector<vector<int>>& cuboids, int last) {
        if(last == cuboids.size()) return 0;
        if(dp[last] != -1) return dp[last];
        int res = 0;
        for(int i = last + 1; i < cuboids.size(); i++) {
            if(bigger(cuboids[last], cuboids[i])) {
                res = max(res, solution(cuboids,i));
            }
        }
        return dp[last] = res + cuboids[last][0];
    }
public:
    int maxHeight(vector<vector<int>>& cuboids) { //h, w, l
        for(auto& c : cuboids) {
            sort(c.begin(), c.end(), greater<int>());
        }
        sort(cuboids.begin(), cuboids.end(), greater<vector<int>>());
        memset(dp,-1,sizeof(dp));
        int res = 0;
        for(int i = 0; i < cuboids.size(); i++) {
            res = max(res, solution(cuboids, i));
        }
        return res;
    }
};