我无法理解麻省理工学院开放课件讲座here中规定的文本对齐问题的动态编程解决方案 . 该讲座的一些注释是here，而笔记的第3页就是我所指的 .
我认为动态编程意味着你会记住一些计算，这样你就不需要重新计算，从而节省你的时间，但是在演讲中给出的算法中，我没有看到任何使用memoization，只是一大堆深度递归调用，即主要功能是这样的：
DP[i] = min(badness (i, j) + DP[j] for j in range (i + 1, n + 1))
DP[n] = 0
其中 badness 是一个函数，用于确定从行长度中减去单词长度后的未使用空间量 . 对我来说，看起来这个算法计算所有可能的"badness"计算并选择最小的计算，这对我来说似乎是蛮力 . 动态编程通常通过记忆过去的计算给我们带来的好处，所以我们不必重新计算？
1 回答
如果您记住结果，则不必多次计算每个
DP[i].也就是说，
DP[0]"calls"DP[2]例如，DP[1]也是如此 . 在第二次调用DP[2]时，没有必要再次计算它，您只需返回memoized值 .这也使得验证该算法的多项式上界变得容易 . 由于每个
DP[i]将执行O（n）操作，并且它们有n，因此整体算法为O（n ^ 2），当然假设badness(i, j)是O（1） .