改进箱式工厂解决方案

Question

箱式工厂是Google 2012第1C轮中的一个问题。它类似于最长的公共子序列问题，并给出了一个O(n^4)解。然而，在分析的最后，它说，另一个改进可以将这再次减少到O(n^3)。我想知道如何对解决方案进行优化。

Answer 1

O(n^4)算法

动态规划方法解决了fx =最大数量的玩具，可以放在盒子中使用的第一个x运行的盒子和第一个y运行的玩具。

它通过考虑在a+1和x之间运行的最后一种类型的盒子，以及在b+1和y之间运行的最后一种类型的玩具来解决这个问题。

O(n^4)算法遍历a和b的所有选择，但我们可以通过只考虑a和b的临界值来简化。

O(n^3)算法

关键是，如果我们有a，b这样，我们有更多的盒子比玩具，那么就没有必要改变a得到更多的盒子(因为这将永远不会帮助我们生产更多的产品)。同样，如果我们有更多的玩具，而不是盒子，那么我们可以跳过考虑所有的b的情况，这会给我们更多的玩具。

这就给出了内环的O(n)算法，在该算法中，我们跟踪了a，b在有更多玩具和有更多盒子之间的边界。这很简单，因为我们可以从a=x-1和b=y-1开始，然后根据我们现在是否有更多的玩具或盒子来减少a或b。(如果等于，则可以将两者都减少。)

算法的每一步都会减少a或b 1，因此这个迭代将需要x+y步骤，而不是原始方法的x*y步骤。

对于x，y的所有值都需要重复，所以总的复杂度是O(n^3)。

额外改进

进一步的改进将是存储每个类型上一次运行的索引，因为这将允许将算法的几个步骤折叠为一个移动(因为我们知道，只有当我们返回到正确类型的运行时，我们的分数才能提高)。然而，在最坏的情况下(所有相同类型的盒子/玩具)，这仍然是O(n^3)。

另一个实际的改进是合并在连续的位置上类型相同的任何运行，因为这可能大大简化测试用例，以暴露以前改进中最坏的情况行为。