面试题 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个。

Python:
1.回溯超时

class Solution:
    def pileBox(self, box: List[List[int]]) -> int:
        highest = 0
        def backtrace(box, high):
            if not box:
                nonlocal highest
                if high > highest:
                    highest = high
                return 
            for i in range(len(box)):
                high += box[i][2]
                temp = [item for item in box if item[0] < box[i][0] and item[1] < box[i][1] and item[2] < box[i][2]]
                backtrace(temp, high)
                high -= box[i][2]
        backtrace(box, 0)
        return highest

2.动态规划

class Solution:
    def pileBox(self, box: List[List[int]]) -> int:
        dp = [0 for i in range(len(box))]
        box.sort(key=lambda x: x[2])
        dp[0] = box[0][2]
        for i in range(1, len(box)):
            temp = [dp[j] for j in range(i-1, -1, -1) if box[j][0] < box[i][0] and box[j][1] < box[i][1] and box[j][2] < box[i][2]]
            temp.append(0)
            dp[i] = box[i][2] + max(temp)
        return max(dp)