我们可以使用贪心算法而不是动态规划来解决“整齐打印”问题吗？

《算法导论》书中的“打印整齐”问题是通过动态规划来解决的。是问题5.3，已找到解决方案here https://segue.middlebury.edu/repository/viewfile/polyphony-repository___repository_id/edu.middlebury.segue.sites_repository/polyphony-repository___asset_id/5299281/polyphony-repository___record_id/5299282/polyphony-repository___file_name/PrintingNeatly.pdf

我认为这个问题可以通过贪心算法简单地解决。每行放入尽可能多的单词，直到无法容纳下一个单词为止，然后移至新行。

有人可以帮助我理解这个解决方案是否足够吗？ （贪心算法）

问题是：打印整齐

考虑在打印机上整齐地打印一个段落的问题。输入文本是长度为 l1,l2,...,ln 的 n 个单词的序列，以字符为单位。我们希望将此段落整齐地打印在多行上，每行最多包含 M 个字符。我们的“整洁”标准如下。如果给定行包含单词 i 到 j，并且我们在单词之间留出一个空格，则该行末尾的额外空格字符数是 M 与单词中的字符总数加上单词之间的空格数之间的差值。我们希望最小化除最后一行之外的所有行中行尾额外空格字符数量的立方之和。给出一个动态编程算法，在打印机上整齐地打印一段 n 个单词。分析算法的运行时间和空间要求。

不，因为贪婪算法经常出现这种情况，现在短视的决策（决定当前行有多少单词）最终会迫使以后付出更高的成本。例如，假设每行可以有 10 个字符。

贪心解

xx xxx xx    cost = 1
xxxxx        cost = 125
xxxxx        cost = 0 (last line)

更好的解决方案

xx xxx       cost = 64
xx xxxxx     cost = 8
xxxxx        cost = 0 (last line)

贪婪的解决方案将更多的单词打包到第一行，但这实际上会产生更高的总解决方案成本。