面试题 08.13. 堆箱子

题目

堆箱子。给你一堆n个箱子，箱子宽 wi、深 di、高 hi。箱子不能翻转，将箱子堆起来时，下面箱子的宽度、高度和深度必须大于上面的箱子。实现一种方法，搭出最高的一堆箱子。箱堆的高度为每个箱子高度的总和。

输入使用数组[wi, di, hi]表示每个箱子。

示例1:
输入：box = [[1, 1, 1], [2, 2, 2], [3, 3, 3]]
输出：6

示例2: 输入：box = [[1, 1, 1], [2, 3, 4], [2, 6, 7], [3, 4, 5]]
输出：10

提示:
箱子的数目不大于3000个。

题解

public int pileBox(int[][] box) {
    // 将箱子按照高度升序排序
    Arrays.sort(box, Comparator.comparingInt(b -> b[2]));

    // 动态规划
    int[] dp = new int[box.length];
    // 第一个箱子最大高度为本身
    int result = dp[0] = box[0][2];

    for (int i = 1; i < box.length; i++) {
        // 长宽高小于i的最大箱子高度
        int max = 0;
        for (int j = 0; j < i; j++) {
            // 找到长宽高小于i的最大箱子高度
            if (box[i][0] > box[j][0] && box[i][1] > box[j][1] && box[i][2] > box[j][2]) {
                max = Integer.max(max, dp[j]);
            }
        }
        // 前i个箱子可以堆叠的最大高度
        dp[i] = max + box[i][2];
        // 所有箱子可堆叠的最大高度
        result = Integer.max(result, dp[i]);
    }

    return result;
}