https://leetcode.com/problems/maximum-height-by-stacking-cuboids/ from Samsung

Thinking process:

First thing is to check the constraints. The size of input N <= 100, which means we can afford at most N^3 algorithm, or C*N^3 when C <= 10.

Now, the question mentioned that You can rearrange any cuboid's dimensions by rotating it to put it on another cuboid, and since we need to satisfy width_i <= width_j and length_i <= length_j and height_i <= height_j, it seems to me we’ll need a 3-D dp? (if you don’t understand why, don’t worry, we’ll get there pretty soon)

If we have a 3-D dp, we have N^3 states, and then we need to at least iterate through our input once, and if we need to look into all the states for every iteration, the total time complexity will be N^4, which is not acceptable.

So, at this time, we might need to think of fixing some dimension, so that we reduce a dimension and thus achieve the N^3 time complexity. We do this by fixing the longest side as the height, and always start from the tallest one. The reason why we fix the logest side as the height is like below

Once we know that the logest side must be the height, it’s straightforward that we want to start from tallest one as the bottom. Now, we only care about the previous width and length if we know that height is always equal or smaller than previous one.

We then define dp[i][j] as the maximum height we can achieve with length = i and width = j, so when we are at (i,j), we want to find (x, y) where x >= i and y >= j as the bottom one and calculate the new height. For example:

Here is the code.

 1class Solution {
 2public:
 3    vector<vector<int>> dp;
 4    int maxHeight(vector<vector<int>>& c) {
 5        dp.resize(101, vector<int>(101));
 6        for (auto& v : c) {
 7            sort(v.rbegin(), v.rend());
 8        }
 9        sort(c.rbegin(), c.rend());
10        int ans = 0;
11        for (auto v : c) {
12            for (int i=v[1]; i<101; i++) {
13                for (int j=v[2]; j<101; j++) {
14                    dp[v[1]][v[2]] = max(dp[v[1]][v[2]], dp[i][j] + v[0]);
15                    ans = max(ans, dp[v[1]][v[2]]);
16                }
17            }
18        }
19        return ans;
20    }
21};