我在理解MIT公开课讲座这里中指定的文本调整问题的动态规划解决方案时遇到了麻烦。来自那个讲座的一些笔记在这里, 我指的是笔记的第3页。
我认为动态规划意味着你记忆一些计算,这样你就不需要重新计算,从而节省时间,但在讲座中给出的算法中,我没有看到任何使用备忘录的地方,只有一堆深递归调用,即主函数是这样的:
我认为动态规划意味着你记忆一些计算,这样你就不需要重新计算,从而节省时间,但在讲座中给出的算法中,我没有看到任何使用备忘录的地方,只有一堆深递归调用,即主函数是这样的:
DP[i] = min(badness (i, j) + DP[j] for j in range (i + 1, n + 1))
DP[n] = 0
其中badness
是一个函数,用于确定从行长度中减去单词长度后未使用空间的数量。在我看来,这个算法计算了所有可能的“badness”值并选择了最小的一个,这似乎是一种暴力方法。动态规划通常通过记忆过去的计算结果来避免重新计算,那么它的优势在哪里?