Question
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.
Example 1:
Input: cuboids = [[50,45,20],[95,37,53],[45,23,12]]
Output: 190
Explanation:
Cuboid 1 is placed on the bottom with the 53x37 side facing down with height 95.
Cuboid 0 is placed next with the 45x20 side facing down with height 50.
Cuboid 2 is placed next with the 23x12 side facing down with height 45.
The total height is 95 + 50 + 45 = 190.
Example 2:
Input: cuboids = [[38,25,45],[76,35,3]]
Output: 76
Explanation:
You can't place any of the cuboids on the other.
We choose cuboid 1 and rotate it so that the 35x3 side is facing down and its height is 76.
Example 3:
Input: cuboids = [[7,11,17],[7,17,11],[11,7,17],[11,17,7],[17,7,11],[17,11,7]]
Output: 102
Explanation:
After rearranging the cuboids, you can see that all cuboids have the same dimension.
You can place the 11x7 side down on all cuboids so their heights are 17.
The maximum height of stacked cuboids is 6 * 17 = 102.
Constraints:
n == cuboids.length
1 <= n <= 100
1 <= widthi, lengthi, heighti <= 100
Algorithm
This question is related to 354 Russian Doll Envelopes, expanding from a 2-D issue to 3-D issue.
因为题目允许任意旋转长方体，我们尝试将每个长方体的六个旋转变种都考虑进来。这样总共有6n个cuboids。
因为从下往上堆叠的次序必须是按照长度递减的，和Envelopes题目一样，都需要排序。 所以我们自然会将所有的6n个cuboids按照长度降排列。就像Envelopes题目里把信封按长和宽排序一样，只是从2维到3维，多一层排序条件。
那么对于长度相同的长方体呢？我们可以再按宽度降序排列；对于宽度也相同的长方体，按照高度降序排列。这样，符合要求的堆叠方案必然是这个序列的一个subsequece。注意，并不是说这个序列的任何一个subsequence都是符合要求的堆叠方案。
Code
Python version
# Time: O(n^2)
# Space: O(n)
class Solution(object):
def maxHeight(self, cuboids):
"""
:type cuboids: List[List[int]]
:rtype: int
"""
for cuboid in cuboids:
cuboid.sort()
cuboids.append([0, 0, 0])
cuboids.sort()
dp = [0]*len(cuboids)
for i in xrange(1, len(cuboids)):
for j in xrange(i):
if all(cuboids[j][k] <= cuboids[i][k] for k in xrange(3)):
dp[i] = max(dp[i], dp[j]+cuboids[i][2])
return max(dp)C++ version
class Solution {
public:
int maxHeight(vector<vector<int>>& cuboids)
{
int n = cuboids.size();
vector<array<int,4>>p;
for (int i=0; i<cuboids.size(); i++)
{
auto c = cuboids[i];
p.push_back({c[0], c[1], c[2], i});
p.push_back({c[0], c[2], c[1], i});
p.push_back({c[1], c[0], c[2], i});
p.push_back({c[1], c[2], c[0], i});
p.push_back({c[2], c[0], c[1], i});
p.push_back({c[2], c[1], c[0], i});
}
sort(p.begin(), p.end());
vector<int>dp(6*n);
for (int i=0; i<6*n; i++)
{
dp[i] = p[i][2];
for (int j=0; j<i; j++)
if (p[j][0]<=p[i][0] && p[j][1]<=p[i][1] && p[j][2]<=p[i][2] && p[j][3]!=p[i][3])
dp[i] = max(dp[i], dp[j]+p[i][2]);
}
int ret = 0;
for (int i=0; i<6*n; i++)
ret = max(ret, dp[i]);
return ret;
}
};