这个文本对齐的动态规划解决方案只是暴力算法吗？

Question

4

我在理解MIT公开课讲座这里中指定的文本调整问题的动态规划解决方案时遇到了麻烦。来自那个讲座的一些笔记在这里, 我指的是笔记的第3页。

我认为动态规划意味着你记忆一些计算，这样你就不需要重新计算，从而节省时间，但在讲座中给出的算法中，我没有看到任何使用备忘录的地方，只有一堆深递归调用，即主函数是这样的：

DP[i] = min(badness (i, j) + DP[j] for j in range (i + 1, n + 1))
DP[n] = 0

其中badness是一个函数，用于确定从行长度中减去单词长度后未使用空间的数量。在我看来，这个算法计算了所有可能的“badness”值并选择了最小的一个，这似乎是一种暴力方法。动态规划通常通过记忆过去的计算结果来避免重新计算，那么它的优势在哪里？

- jcm

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Juan Lopes · Accepted Answer

如果你记忆化结果，就不需要多次计算每个DP[i]。

也就是说，DP[0]会“调用”DP[2]，DP[1]也会这样做。第二次调用DP[2]时，无需再次计算它，只需返回记忆化的值即可。

这还使得验证此算法的多项式上界变得容易。由于每个DP[i]将执行O(n)个操作，而且有n个这样的操作，因此总体算法复杂度为O(n^2)，当然，前提是badness(i, j)是O(1)。