面试题 08.13.堆箱子

1. 题目描述

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

标签 数组 动态规划 排序

2. 解题

先将箱子按wi进行排列（从小到大），从而问题转化为LIS（最长上升自序列问题）。

LIS（最长上升自序列问题） 见topic300