arrays - 在一个段落中添加 N 个换行符以获得最窄的结果

Question

假设我们有这样一段:

Lorem ipsum dolor sit amet, consectetur adipiscing elit, sed do eiusmod tempor incididunt ut labore et dolore magna aliqua. Ut enim ad minim veniam, quis nostrud exercitation ullamco laboris nisi ut aliquip ex ea commodo consequat. Duis aute irure dolor in reprehenderit in voluptate velit esse cillum dolore eu fugiat nulla pariatur. Excepteur sint occaecat cupidatat non proident, sunt in culpa qui officia deserunt mollit anim id est laborum.

假设一个固定宽度的字体，我们想要恰好添加 N 个换行符(仅通过替换空格字符)来生成 N+1 行文本 block 。

这是 N=8 的输出示例，我们得到的最大线宽为 51:

Lorem ipsum dolor sit amet, consectetur adipiscing 
elit, sed do eiusmod tempor incididunt ut labore 
et dolore magna aliqua. Ut enim ad minim veniam, 
quis nostrud exercitation ullamco laboris nisi ut 
aliquip ex ea commodo consequat. Duis aute irure 
dolor in reprehenderit in voluptate velit esse 
cillum dolore eu fugiat nulla pariatur. Excepteur 
sint occaecat cupidatat non proident, sunt in culpa 
qui officia deserunt mollit anim id est laborum.

我们如何找到用换行符替换哪些空格字符以获得最窄(最长行上的最少字符数)且尝试次数最少？

Answer 1

假设文本由 m 个单词组成，我们将从 1 到 m 编号。将 f(i, j) 定义为仅由前 i 个单词组成的子问题的最佳(最小宽度)解决方案中任何行的最大宽度(以字符为单位)，条件是正好使用 j 个换行符。那么整个问题的最佳可能中断序列的宽度将由 f(m, n) 给出。这可以使用 dynamic programming 相当有效地解决。 .

设单词 i 和单词 j >= i 之间的片段的字符总长度为 len(i, j)。 (这很容易计算:只需计算一个包含 m+1 个值的数组 len0[j]，其中 0 <= j <= m，每个值给出由前 j 个单词组成的片段的字符总长度；然后 len( i, j) 只是 len0[j] - len0[i-1] - 1，约定 len0[0] = -1。)

基本情况很简单:

f(i, 0) = len(0, i)   (i.e., if there are no line breaks)

递归情况是:

f(i, j) = the minimum over all 0 <= k < i of max(f(k, j-1), len(k+1, i))

也就是说，要找到将前 i 个单词分成 j+1 行的最佳方法(即使用 j 个换行符)，我们可以对每个较短的 k 字前缀尝试以下操作:确定最好的拆分方法k 词前缀到 j 行(即使用 j-1 换行符)，并将我们从中获得的最大宽度与将其余 i-k 词放在最后一行的宽度进行比较。每个前缀都为我们提供了不同的候选解决方案，因此我们可以从中选出最好的。

构建解决方案

现在我们可以计算最佳宽度 f(m, n)，我们如何使用它来实际构建解决方案？幸运的是，在动态规划中有一个标准技术可以做到这一点。最快的方法是在计算 f(i, j) 的过程中，记录(实际上是 a，因为通常可能有多个最优解)k 的值在前导表中产生最小值预 [i][j]。计算出 f(m, n) 并填写前导表后，我们可以通过向后遍历它来构造一个最优解:pred[i][j] 告诉我们一个值 k，这样我们就可以通过添加在单词k之后有一个换行符，所以在那里添加一个换行符，然后查看pred[k][j-1]找到上一个换行符的位置，继续直到j到达0。

时间和空间复杂度

如果递归是memoised使用动态规划，那么最多有 O(mn) 个不同的参数组合可以调用 f()(i 的范围在 0 和 m 之间，j 的范围在 0 和 n 之间)，并且递归调用之外花费的时间是O(m)(k 的取值范围为 0 到 m，k 的每个值的计算量为 O(1))，因此此解的时间复杂度为 O(nm^2)。 空间复杂度为 O(mn)，但是通过切换到自下而上的 DP，这可以很容易地减少到 O(m)，因为在计算 f(i, j) 我们只需要访问第二个参数为 j-1 的 f() 的值，这意味着实际存储计算值 f(q, j-1) 的 size-(m+1) 数组就足够了对于 0 <= q <= m。