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

Question

假设我们有这样一段话：

Lorem ipsum dolor坐在那里，圣职献祭，圣职献祭，圣职献祭，圣职献祭，圣职献祭，圣职献祭，圣职献祭，圣职献祭，圣职献祭，圣职献祭，圣职献祭，圣职献祭，圣职献祭，圣职献祭，圣职献祭，圣职献祭，圣职献祭，圣职献祭，圣职献祭，圣职献祭，圣职献祭，圣职献祭，圣职献祭在有限的条件下，在有限的条件下，在有限的条件下进行锻炼。杜伊斯奥特鲁尔杜洛在谴责在波罗的海韦尔特埃塞西莱姆杜洛雷欧盟逃犯nulla pariatur。例外的情况下，不存在，必须在错误的地方，在错误的地方，莫利特和其他地方。

假设字体为固定宽度，我们希望精确地添加N个换行符（仅替换空格字符），以生成一个n1行的文本块。

下面是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字符数，并且您想要插入N换行符。然后得到尽可能短的线宽：L_min=RoundToInfinity（（M-N）/N1）（N-M因为我们清除了N空格）
• 用单词填充每行，使线宽小于或等于L_min。这样，您的最后一行将包含更多的字符，然后其他。
• 现在总是搜索最大的一行（开始时这将是最后一行），把它的第一个单词放在前一行的和处。重复，直到第一行最长。
• 在任何时候，您都应该存储您的实际最大线宽L，这样您就可以恢复L最小时的情况。

Answer 2

（从这里改编，如何以最小化每个分区总和最大值的方式对整数数组进行分区？）

如果我们将单词长度视为数字列表，我们可以二进制搜索分区。

我们的max length范围从0到sum（字长列表）（num words-1），表示空格<代码>中间=（范围/2）。我们检查是否可以通过在O（m）时间中划分为N个集合来实现mid：遍历列表，在当前总和小于或等于mid时，将（单词长度1）添加到当前部分。当总和超过mid时，开始新的部分。如果结果包括N或更少的部分，则可以实现mid。

如果可以达到mid，请尝试较低的范围；否则，范围会更大。时间复杂度为O（m log num\u chars）。（您还必须考虑如何删除每个部分的空间，即折线将在哪里进行计算。

Answer 3

假设文本由m个单词组成，我们将从1到m编号。定义f（i， j）为子问题的最优解（最小宽度）中任意行的最大宽度（以字符为单位），该子问题仅由前i个单词组成，但限制条件是使用精确的j换行符。然后，整个问题的最佳中断序列的宽度将由f（m，n）给出。这可以用动态规划来相当有效地解决。

设单词i和单词j之间片段的总长度（以字符为单位）

基本情况很简单：

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）的过程中，记录在前一个表pred[i][j]中产生最小值的k值（实际上是a，因为通常可能存在多个最优解）。计算f（m，n）并填写前置表后，我们可以通过向后遍历来构造最优解：pred[i][j]告诉我们一个值k，这样我们可以通过在单词k之后添加换行符来生成最优解，因此在那里添加换行符，然后查看pred[k][j-1]以找到上一个换行符的位置，继续，直到j达到0。

如果递归是使用动态编程记忆的，那么最多有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）时，我们只需要访问f（）的值，其中第二个参数是j-1，这意味着它足以实际存储大小-（m1）数组计算值f（q，j-1）为0