题目描述
leetcode 困难题
给你 n 个长方体 cuboids ，其中第 i 个长方体的长宽高表示为 cuboids[i] = [widthi, lengthi, heighti]（下标从 0 开始）。请你从 cuboids 选出一个 子集 ，并将它们堆叠起来。
如果 widthi <= widthj 且 lengthi <= lengthj 且 heighti <= heightj ，你就可以将长方体 i 堆叠在长方体 j 上。你可以通过旋转把长方体的长宽高重新排列，以将它放在另一个长方体上。
返回 堆叠长方体 cuboids 可以得到的 最大高度 。
示例1：
1
2
3
4
5
6
7
| 输入：cuboids = [[50,45,20],[95,37,53],[45,23,12]]
输出：190
解释：
第 1 个长方体放在底部，53x37 的一面朝下，高度为 95 。
第 0 个长方体放在中间，45x20 的一面朝下，高度为 50 。
第 2 个长方体放在上面，23x12 的一面朝下，高度为 45 。
总高度是 95 + 50 + 45 = 190 。
|
提示1：
1
2
3
| n == cuboids.length
1 <= n <= 100
1 <= widthi, lengthi, heighti <= 100
|
分析
结论：将每个长方体的最长边作为高度是最优的。
这是因为如果长方体 $c2$ 可以叠在长方体 $c1$ 上面，即存在某种排列 $w2 < w1$ 且 $l2 < l1$ 且 $h2 < h1$，那么将最长边作为高度也一定会满足堆叠条件，并且由于更上方的长方体 $c3$ 也必须满足条件 $w3,l3,h3 < h2$，所以类似前面所说的，更上方的长方体也必然是将最长边作为高度才是最优的。
因此最优的堆叠方法一定是基于最长边作为高度的。
动态规划
由于因此最优的堆叠方法一定是基于最长边作为高度的。
设 $dp[i]$ 表示以第 $i$ 个长方体作为最底部长方体的最大高度，$dp$ 从 $1$ 开始，此时类似 LC-300-最长递增子序列，转移方程为
$$
\begin{align}
&dp(i) = max\{dp(j)\} + curHeight 1 <= j < i and w_{j-1} < w_{i-1} and l_{j-1} < l_{i-1}\\
\end{align}
$$
需要注意的是，LC-300-最长递增子序列 由题目性质保证了能出现在子序列前方的元素下标必然小于当前元素下标。那么类似的，本题也需要保证在计算到某个 $dp[i]$ 时，能堆叠在当前长方体上面的状态已经全部计算完毕，也就是说要先对长方体数组进行排序，使满足 $w_j <= w_i, l_j <= l_i, h_j <= h_i$ 时，也必然满足 $j <= i$ 。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| class Solution {
public int maxHeight(int[][] cuboids) {
IntStream.range(0, cuboids.length).forEach(i -> Arrays.sort(cuboids[i]));
Arrays.sort(cuboids, Comparator.<int[]>comparingInt(arr -> arr[2])
.thenComparingInt(arr -> arr[1])
.thenComparingInt(arr -> arr[0]));
int[] dp = new int[cuboids.length + 1];
for(int i = 1; i < cuboids.length + 1; i++){
dp[i] = cuboids[i - 1][2];
for(int j = 1; j < i; j++){
if(cuboids[i - 1][0] >= cuboids[j - 1][0] && cuboids[i - 1][1] >= cuboids[j - 1][1]){
dp[i] = Math.max(dp[i], dp[j] + cuboids[i - 1][2]);
}
}
}
return Arrays.stream(dp).max().orElseThrow();
}
}
|
记忆化搜索
类似 $dp$ 解法，也可以采用自顶向下的记忆化搜索，会减少一些无效状态的计算。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
| class Solution {
int[][] cuboids;
int[] mem;
public int maxHeight(int[][] cuboids) {
IntStream.range(0, cuboids.length).forEach(i -> Arrays.sort(cuboids[i]));
Arrays.sort(cuboids, Comparator.<int[]>comparingInt(arr -> arr[2])
.thenComparingInt(arr -> arr[1])
.thenComparingInt(arr -> arr[0]));
this.cuboids = cuboids;
mem = new int[cuboids.length];
Arrays.fill(mem, -1);
return dfs(-1, 0);
}
private int dfs(int top, int cur){
if(cur >= cuboids.length){
return 0;
}
if(top != - 1 && mem[top] != -1){
return mem[top];
}
int ret = dfs(top, cur + 1);
if(top == - 1 || (cuboids[cur][0] >= cuboids[top][0] && cuboids[cur][1] >= cuboids[top][1])){
ret = Math.max(ret, cuboids[cur][2] + dfs(cur, cur + 1));
}
if(top != - 1){
mem[top] = ret;
}
return ret;
}
}
|