leetcode.面试题 08.13. 堆箱子
问题描述
堆箱子。给你一堆n个箱子，箱子宽 wi、深 di、高 hi。箱子不能翻转，将箱子堆起来时，下面箱子的宽度、高度和深度必须大于上面的箱子。实现一种方法，搭出最高的一堆箱子。箱堆的高度为每个箱子高度的总和。
输入使用数组[wi, di, hi]表示每个箱子。
动态规划
思路分析
先对数组进行排序
dp[i] 代表0-i，以i为尾的最大高度
代码实现
DFS
思路分析
剪枝
- 如果当前遍历的结点，whd都不大于上一个结点，则不搜索
- 如果评估值小于当前答案，则不搜索 评估值等于当前已求的高度加上后续的评估高度
记忆