dynamic-programming - 动态规划：最小化空白

Question

这是一个家庭作业问题，但我完全迷路了。我很难弄清楚子问题是什么：我尝试了一种贪婪的方法，我尝试过增加一行中的单词数等等，但我什么也想不出来。任何人都可以提供任何见解吗？

问题：考虑一个将单词列表转换为排版文本的程序。该程序将单词打印到长度为 W 的行上，这样行尾的额外空格量使得包含单词 i 到 j 的行包含 W - j + i - SUM（单词 i 到 j 中的字符）。编写一个动态规划算法，最小化每行额外空格的平方和。

Answer 1

我相信您应该采用的方法如下：

-> 找到长度为 1 的行的最佳解决方案并保存该值。（这应该是微不足道的）。

->以这种方式找到长度为 2 的线的最佳解决方案：

对于每个单词，看看它们是否合适。如果他们确实计算了剩余空间并使用该空间的最佳解决方案（将剩余 1 或 0 个空间）。

...（一直这样做到 W）

->以这种方式找到长度为 W 的线的最佳解决方案：

对于每个单词，看看它们是否合适。如果是这样，请计算剩余空间并使用该剩余空间的最佳解决方案（因为它小于您已经计算过的 W。）

Answer 2

对于开发人员来说，动态编程是轻松解决此类问题的好选择。

我们可以用来解决这个问题的动态规划方法如下。首先，如果所有单词都放在一行上，那么我们就完成了。如果不是，那么我们将尝试所有可能适合这一行的组合，然后我们解决由每个可能组合的剩余单词组成的子问题，我们可以通过最小化第一行的成本来找到最佳布局添加剩余子问题的最小成本。

令 MAX(i) 为其中 最大的 j，这 意味着单词 j 可以放在以单词 i 开头的行上。我们可以填充成本 c 的 n 元素数组，其中 c[i] 是打印单词 i 到 n 的最小成本，如下所示： 如果 MAX(i) = n，则 c[i] = 0 else :
填充从 n 到 1 的数组从上到下，将花费 O((M/2)n) 时间，因为最多 M/2 个单词可以放在一行中。所需空间为 O(n)。