我为O（n ^ 2）中的盒排序算法写了另一种证明，并通过归纳证明。

有人可以反驳/提供解决方案的另一种证明吗？

问题-

为您提供了n种矩形3-D框的集合，其中第i个框的高度为h（i），宽度w（i）和深度d（i）（所有实数）。所有长度都不同，并且宽度都不同。您想创建一堆尽可能高的盒子，但只能在顶部放置一个盒子如果下部盒子的2-D基座的尺寸均严格大于上部盒子的2-D基座的尺寸，则可以选择另一个盒子。您可以不要旋转盒子，以便任何侧面功能作为其基础。

已知解决方案-

• 通过增加底面积对框进行排序。
• 创建一个大小为n的表t，索引为1≤i≤n。以i = n开头 到1，通过对所有j> i的max {h（i），max {h（i）+ t [j]}定义t [i]，使得w（j）> w（i）和l（j）> l（i）}
• 返回以下值：max {t [1]，。 。 。 ，t [n]}

我的解决方案-

• 按数组W的宽度递增和长度递增的顺序对框进行排序 在数组L中。
• 创建一个nxn矩阵，其中t [i，j] =最高 在L（i）长和W（j）宽的基座上构建的堆栈。
• 答案将在t [n，n]中，因为那是我们的最大可能基数 区域。

• 对于矩阵的第一行（这是 可以在最小长度的基础区域上构建的最高堆栈- 意味着只有最小长度的盒子可以在其中）

  定义t [1，j]：

  • 0

  • 具有最小长度的框的高度 =框的宽度

• 对于矩阵的第一列（这是 可以在最小宽度的基础区域上构建-仅意味着框 最小宽度可以在其中）

  定义t [i，1]：

  • 0
  • 具有最小宽度的框的高度 =具有最小宽度的框的长度

• 定义t [i，j] =框的高度，框的长度为L（i），宽度为 W（j），如果存在+ max {t [i-1，j]，t [i，j-1]}

  • 只有一个具有这些属性的框，因为它们都是唯一的。

谢谢大家！