堆箱子.md

面试题 08.13. 堆箱子

https://leetcode-cn.com/problems/pile-box-lcci/

题目描述

堆箱子。给你一堆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个。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/pile-box-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

 动态规划
 初始化dp数组为当前盒子的高度
 对第i个盒子，判断0~i-1个盒子的长宽高是否小于当前盒子
 如果满足条件，就更新dp数组

python代码

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