面试题08.13.堆箱子

链接：面试题08.13.堆箱子
难度：Hard
标签：数组、动态规划、排序
简介：堆箱子。给你一堆n个箱子，箱子宽 wi、深 di、高 hi。箱子不能翻转，将箱子堆起来时，下面箱子的宽度、高度和深度必须大于上面的箱子。实现一种方法，搭出最高的一堆箱子。箱堆的高度为每个箱子高度的总和。

题解 1 - python

• 编辑时间：2023-10-25
• 执行用时：1056ms
• 内存消耗：16.35MB
• 编程语言：python
• 解法介绍：dp[i]表示当前为顶时的最大值。

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