我在理解麻省理工学院开放课件讲座中指定的文本对齐问题的动态编程解决方案时遇到了困难。那堂课的一些笔记是的,我指的是笔记的第三页。
我认为动态编程意味着你记住了一些计算,这样你就不需要重新计算,从而节省了你的时间,但在讲座中给出的算法中,我看不到记忆化的任何用途,只是一大堆深度递归调用,即主函数是这样的:
DP[i] = min(badness (i, j) + DP[j] for j in range (i + 1, n + 1))
DP[n] = 0
其中,badness是一个函数,用于确定从行长中减去单词的长度后的未使用空间量。对我来说,这个算法似乎计算了所有可能的“坏”计算,并选择了最小