堆箱子。给你一堆n个箱子，箱子宽 wi、深 di、高 hi。箱子不能翻转，将箱子堆起来时，下面箱子的宽度、高度和深度必须大于上面的箱子。实现一种方法，搭出最高的一堆箱子。箱堆的高度为每个箱子高度的总和。
输入使用数组[wi, di, hi]表示每个箱子。
示例1:
输入：box = [[1, 1, 1], [2, 2, 2], [3, 3, 3]] 输出：6
class Solution {
public int pileBox(int[][] box) {
Arrays.sort(box, (a, b) -> {return a[0] - b[0];}
);
int[] dp = new int[box.length];
dp[0] = box[0][2];
int ans = dp[0];
for (int i = 1; i < dp.length; i++) {
int max = 0;
for (int j = 0; j < i; j++) {
if (box[j][0] < box[i][0] && box[j][1] < box[i][1] && box[j][2] < box[i][2])
max = Math.max(max, dp[j]);
}
dp[i] = box[i][2] + max;
ans = Math.max(ans, dp[i]);
}
return ans;
}
}
先对这个数组进行一维排序，答案序列一定是这个一维排序序列的子序列。
动态规划，dp[i] 为第 i 个箱子能排出来的最大高度， dp[i] = box[i][2] + max(dp[…], 0) 即找到它之前的最小的。