这道题有点难，但并不是完全难。
题目
堆箱子。给你一堆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个。
分析
箱子有三个维度，一瞬间就让人想到了三维的DP。
能否降低循环层数呢？我们注意到题目中所说的 下面箱子的宽度、高度和深度必须大于上面的箱子 ，那么，只需要根据任意一个维度进行排序，最终箱子叠起来的顺序就是排序后的顺序（正序或反序）。
更具体地说，假如我们以宽度 w 为参照进行降序排序，则当 i < j 时，第 i 个箱子 一定 在第 j 个箱子下面（如果它们都被选中的话），因为第 i 个箱子的宽度更大。
这样，我们就可以少考虑一个维度了。
sort(box.begin(), box.end(), [](const vector<int>& a, const vector<int>& b)
{
return a[0] > b[0];
});
接着，我们考虑深度和高度。
错解
很容易陷入传统DP的思路中：令 dp[w][h] 表示深度 d 、高 h 时所能取得的最大高度，则令最外层箱子下标从 0 到 box.size() - 1 循环，每一次循环都令深度和高度从 1 到 maxDepth or maxHeight 进行循环，那么当前这一箱子，面对深度 d 和高度 h 的时候，取得 dp[d][h] = max(dp[d][h], dp[box[idx][1]][box[idx][2]] + box[idx][2]) 。
理论上，这一状态转换公式来源于一个事实，即当前这一箱子有两种选择：
- 放上去：则留给上一个箱子的空间只剩下
box[idx][1]的深度，以及box[idx][2]的高度，上一个箱子利用这两个数值取到的最大高度是dp[box[idx][1]][box[idx][2]]，加上当前箱子本身的高度box[idx][2]即为这一方案最终取得的高度； - 不放上去：则留给上一个箱子的空间不变。
利用这一思路写出如下的代码：
class Solution {
public:
int pileBox(vector<vector<int>>& box) {
int maxWidth = INT_MIN;
int maxDepth = INT_MIN;
int maxHeight = INT_MIN;
for (auto b : box)
{
maxDepth = max(maxDepth, b[1]);
maxHeight = max(maxHeight, b[2]);
}
sort(box.begin(), box.end(), [](const vector<int>& a, const vector<int>& b)
{
return a[0] < b[0];
});
int dp[maxDepth + 2][maxHeight + 2];
memset(dp, 0, sizeof(dp));
for (int idx = 0; idx < box.size(); idx++)
{
for (int d = maxDepth + 1; d >= 1; d--)
{
for (int h = maxHeight + 1; h >= 1; h--)
{
if (box[idx][1] < d && box[idx][2] < h)
{
dp[d][h] = max(dp[d][h], dp[box[idx][1]][box[idx][2]] + box[idx][2]);
}
}
}
}
return dp[maxDepth + 1][maxHeight + 1];
};
这个代码的问题在于：题目中要求的是下方箱子的各项数值必须 严格大于 上方的箱子。尽管我们进行了排序，相邻箱子的 宽度 仍然可能是相同的！在状态转移的过程中，我们考虑了上一个箱子的深度和高度都严格小于当前箱子，却遗漏了它的宽度。
这就使得我们取到的 dp[box[idx][1]][box[idx][2]] + box[idx][2] 可能同时将当前箱子和上一个箱子都堆上了，而当前箱子与上一个箱子在宽度上是相同的。
这一情况体现在用例 2 中，对宽度进行排序，这一代码将输出答案 12 ，表示将 [1,1,1] 、 [2,3,4] 和 [2,6,7] 这三个箱子都堆上了；而，尽管 [2,3,4] 和 [2,6,7] 在深度和高度上递增，却在宽度上相同，我们的代码无法考虑这一情形。
正解
有一说一，陷入了错解的思路之后，很难自拔，正解来源于题解。
我们需要改变 dp 数组的含义，现在，令它作为一个一维数组， dp[i] 表示将第 i 个箱子置顶时，取得的最大高度。
我们还是将宽度 降序排序 ，如果希望将第 i 个箱子置顶，那么它底下的箱子只可能出现在 0 ~ i - 1 的下标范围内。
每次考虑到一个 i 时，我们就向前遍历 0 ~ i - 1 号箱子，如果某个箱子满足三个维度都大于当前的 i 号箱子，则可以得到一个 dp[n] + box[i][2] 的方案，含义是将第 n 号箱子置顶时的最大高度，加上现在的第 i 号箱子的高度。
这一方法简直是很直观了，但是需要扣几个细节：
dp[0]显然是第0号箱子 置顶 时的最大高度，当前箱子有没有可能不放在任何箱子上呢？当然可能。因此，遍历完0 ~ i - 1号箱子之后，还要将取得的最大方案与box[i][2]进行比较；- 最终返回的答案可不是
dp[box.size() - 1]！有悖于传统的DP方案，这里的dp[box.size() - 1]表示将最后一个箱子置顶时的最大高度，然而最后一个箱子可不一定要被选中，我们应该遍历所有箱子，取得最大值。
AC代码
class Solution {
public:
int pileBox(vector<vector<int>>& box) {
if (!box.size())
return 0;
sort(box.begin(), box.end(), [](const vector<int>& a, const vector<int>& b)
{
return a[0] > b[0];
});
// dp[i] 表示将第i个箱子放在顶部能够取得的最大的高度
// dp[i] = max(dp[n] + box[i][2])
vector<int> dp(box.size(), 0);
dp[0] = box[0][2];
for (int i = 1; i < box.size(); i++)
{
// cout << box[i][0] << " " << box[i][1] << " " << box[i][2] << endl;
for (int n = i - 1; n >= 0; n--) // 遍历所有可能的底部
{
// cout << "\t" << box[n][0] << " " << box[n][1] << " " << box[n][2] << endl;
if (box[n][0] > box[i][0] && box[n][1] > box[i][1] && box[n][2] > box[i][2])
{
dp[i] = max(dp[i], dp[n] + box[i][2]);
}
}
dp[i] = max(dp[i], box[i][2]); // 表示第 i 号箱子不放在任何箱子顶上
}
int res = INT_MIN; // 答案不是 dp[box.size() - 1] ！要循环取得最大值
for (int i = 0; i < box.size(); i++)
{
res = max(dp[i], res);
}
return res;
}
};
参考资料
[1] ffreturn.08.13 c++几乎双百的暴力动态规划[EB/OL].2021-06-01
08.13 c++几乎双百的暴力动态规划 - 堆箱子 - 力扣（LeetCode） (leetcode-cn.com)
[2] knight.【猎豹题解日记】动态规划、回溯两种解法[EB/OL].2020-07-08