盒子堆叠问题
我在很多地方发现了这个着名的dp问题，但我无法弄清楚如何解决。
给出一组n个矩形三维框，其中第i框有高度h（i），宽度w（i）和深度d（i）（所有实数）。 你想创build一堆尽可能高的盒子，但是如果下盒子的二维底座的尺寸每个都严格大于二维底座的尺寸，那么你只能在另一个盒子的顶端堆叠一个盒子。更高的箱子的D基地。 当然，你可以旋转一个盒子，以便任何一方作为其基础。 也可以使用同一types盒子的多个实例。
这个问题对我来说似乎太复杂了，以找出步骤。 因为它是3D，我得到三个高度，宽度和深度的序列。 但是，因为有可能交换三维，所以对我来说问题变得更加复杂。 所以请有人解释在没有交换时解决问题的步骤，然后在交换时如何解决问题。 我对这个问题感到厌倦。 所以，请有人解释简单的解决scheme。
我想你可以使用dynamic编程最长的子序列algorithm来解决这个问题： http : //www.algorithmist.com/index.php/Longest_Increasing_Subsequence
考虑到旋转很容易：对于每一个塔，你必须检查的是，如果你使用它的高度作为底部的长度和宽度作为高度会发生什么，如果以自然的方式使用它会发生什么情况。 例如：
============= = = = = = = L = H = = = = = ============= W 成为像（是的，我知道它看起来不像是应该的，只是按照符号）：
================== = = = = = W = L = = = = ================== H
因此，对于每个块，实际上有3个块代表其可能的旋转。 根据这个调整你的块数组，然后通过减less基地面积进行sorting，并应用DP LISalgorithm来获得最大高度。
适应的递推是：D [i] =如果最后的塔必须是我们可以获得的最大高度。
D[1] = h(1); D[i] = h(i) + max(D[j] | j < i, we can put block i on top of block j) Answer is the max element of D.
看到一个video解释这里： http ://people.csail.mit.edu/bdean/6.046/dp/
堆栈可以看作是x，y，z三元组（x，y是2D平面，z是高度）的序列，其中x（i）> x（i + 1）和y（i）> y I + 1）。 我们的目标是最大化从三组可用的三元组中选取三元组的总和 – 每个三元组是在特定方向上的一种types的组合。 很容易看到，执行约束x> y不会减less解决scheme空间。 所以每个盒子产生3个三元组，每个元素都有w，h，d作为z坐标。
如果把三元组看作是一个有向无环图，当它们之间满足x，y约束条件时，长度为z的边存在于两个三元组之间，那么问题是find通过该图的最长path。
我们首先尝试在二维中解决这个问题：
说你有X和Y的矩形，问题是相似的（最高的塔，但这次你只需要担心一个基本维度）。
因此，首先，您将遍历整个集合，除了方块（其中X（1）= X（2）&& Y（1）= Y（2））旋转90度（交换X和Y） 。 这代表所有可能的变化。
那么你按他们的X方排列他们，从最大到最小。 在X值重复的情况下，删除Y值较小的值。
同样的原则适用于三维场景，只有现在你不只是乘以集合的大小6（W，H，D的每个可能的变种），而是2，你做这个通过消除所有的变化，其中宽度较低比深度（对于每个我，W（i）> = D（i）），然后消除高度不是最高也不是最低的变化（因为其他两个变化可以去一个另一个的顶部，这个不能join）。 （1）= W（2）&& H（1）= H（2）&& D（1）= D（2））。
那么你应该按照宽度进行sorting，只有这一次你不要扔掉相同宽度的变化（因为一个可能适合另一个不可能的塔），那么你可以使用LIValgorithm，如上面的@IVlad所述：
D[1] = h(1); D[i] = h(i) + max(D[j] | j <= i and we can put tower i on tower j) or simply h(i) if no such D[j] exists.
诀窍是，你知道宽度是两者中最长的，所以你知道第一个元素不适合任何后面的元素。
我build议你创build一个树（或某种树形结构），并用深度search来parsing它，从各个垂直“高度”（取决于旋转）值计算最大高度。
这（我认为这是基本的方法）。
详细信息：
树根应该是任何立方体都适合的地面。 从那里你可以创build下一个可能的子节点（可以放置在当前框的某个顶点上的框）框。 recursion地为每个框和旋转做。
当树被build造时，通过它并且计算从地板到树的叶子的总塔高。
解决问题的办法包括三个步骤。
- 对每个盒子的尺寸进行sorting，以便比较任意两个盒子，以便比较其对应的尺寸。
- 按照字典顺序对文本框顺序进行sorting，以便对于每个文本框，左边的框都是可能适合的框。
- 应用最长增加子
O(n^2)的O(n^2)algorithm 。
第三步是最昂贵的，并且将解决scheme的复杂性提高到O(n^2) 。 如果您想阅读关于该方法的完整说明，每个步骤如何帮助您find答案，以及完整的代码，请查看我撰写的有关该问题的博文 。
