Box Factory是 Google Code Jam 2012 Round 1C 中的一个问题。它类似于最长公共子序列问题，他们给出了一个O(n^4) 的解决方案。但是，在分析结束时，它说另一项改进可以再次将其减少到 O(n^3)。我想知道可以对解决方案进行哪些优化。
问问题
384 次
1 回答
3
O(n^4) 算法
动态规划方法求解 f[x][y] = 使用前 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)。
另一个实际的改进是合并在连续位置上类型相同的任何运行，因为这可以显着简化旨在揭示先前改进中最坏情况行为的测试用例。
于 2012-07-22T12:08:27.263 回答