在一个段落中添加 N 个换行符以获得最窄的结果
Adding N line breaks in a paragraph for the narrowest result
假设我们有这样一段：
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 个换行符（仅通过替换 space 个字符）来生成 N+1 行文本块。
这是 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.
我们如何找到用换行符替换哪些 space 个字符以获得最窄（最长行上的最少字符数）且尝试次数最少？
假设文本由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) 的过程中，记录下在前身 table pred[i][j]。计算出 f(m, n) 并填入前导 table 后，我们可以通过向后遍历它来构造一个最优解：pred[i][j] 告诉我们一个值 k，这样我们就可以产生一个最优解是在单词k之后加一个换行符，所以在那里加一个换行符，然后看pred[k][j-1]找到上一个换行符的位置，继续下去直到j到0.
时间和 space 复杂度
如果递归memoised使用动态规划，那么最多有 O(mn) 个不同的参数组合可以调用 f()（i 的范围在 0 到 m 之间，j 的范围在0 和 n)，在递归调用之外花费的时间是 O(m)（k 的范围在 0 到 m 之间，k 的每个值的计算是 O(1)），所以 时间这个解决方案的复杂度是 O(nm^2)。 space 复杂度为 O(mn)，但是通过切换到自下而上的 DP，这可以很容易地降低到 O(m)，因为在计算 f(i, j) 时，我们只需要访问第二个参数为 j-1 的 f() 的值，这意味着实际存储大小为 (m+1) 的数组就足够了0 <= q <= m.
的计算值 f(q, j-1)
我的试错尝试。
我不太确定你是否总是得到最短的线宽，但该算法快速且易于 understand/implement。而且我认为在大多数情况下这应该符合需求
- 假设您有
M 个字符，并且您想要插入 N 个换行符。然后你得到最短的线宽：L_min = RoundToInfinity((M-N)/N+1)（N-M因为我们清除了N个空格）
- 用文字填充每行，使线宽小于或等于
L_min。这样你的最后一行将包含比其他更多的字符。
- 现在总是搜索最大的行（开始时这将是最后一行），取出它的第一个单词并将其放在上一行的和处。重复直到第一行最长。
- 任何时候你都应该存储你的实际最大线宽
L，这样你就可以恢复L最小时的情况。
（改编自此处，）
如果我们将单词长度视为数字列表，我们可以对分区进行二分查找。
我们的 max length 范围从 0 到 sum (word-length list) + (num words - 1), meaning the spaces。 mid = (range / 2)。我们检查 mid 是否可以通过在 O(m) 时间内划分为 N 集合来实现：遍历列表，将 (word_length + 1) 添加到当前部分，而当前总和小于或等于 mid。当总和通过mid时，开始新的部分。如果结果包含 N 或更少的部分，则 mid 是可以实现的。
如果可以达到mid，请尝试较低的范围；否则，更高的范围。时间复杂度为O(m log num_chars)。 （您还必须考虑如何删除每个部分的 space，这意味着换行符的位置，计算中的特征。）
假设我们有这样一段：
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 个换行符（仅通过替换 space 个字符）来生成 N+1 行文本块。
这是 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.
我们如何找到用换行符替换哪些 space 个字符以获得最窄（最长行上的最少字符数）且尝试次数最少？
假设文本由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) 的过程中，记录下在前身 table pred[i][j]。计算出 f(m, n) 并填入前导 table 后，我们可以通过向后遍历它来构造一个最优解：pred[i][j] 告诉我们一个值 k，这样我们就可以产生一个最优解是在单词k之后加一个换行符，所以在那里加一个换行符，然后看pred[k][j-1]找到上一个换行符的位置，继续下去直到j到0.
时间和 space 复杂度
如果递归memoised使用动态规划，那么最多有 O(mn) 个不同的参数组合可以调用 f()（i 的范围在 0 到 m 之间，j 的范围在0 和 n)，在递归调用之外花费的时间是 O(m)（k 的范围在 0 到 m 之间，k 的每个值的计算是 O(1)），所以 时间这个解决方案的复杂度是 O(nm^2)。 space 复杂度为 O(mn)，但是通过切换到自下而上的 DP，这可以很容易地降低到 O(m)，因为在计算 f(i, j) 时，我们只需要访问第二个参数为 j-1 的 f() 的值，这意味着实际存储大小为 (m+1) 的数组就足够了0 <= q <= m.
的计算值 f(q, j-1)我的试错尝试。 我不太确定你是否总是得到最短的线宽，但该算法快速且易于 understand/implement。而且我认为在大多数情况下这应该符合需求
- 假设您有
M个字符，并且您想要插入N个换行符。然后你得到最短的线宽：L_min = RoundToInfinity((M-N)/N+1)（N-M因为我们清除了N个空格） - 用文字填充每行，使线宽小于或等于
L_min。这样你的最后一行将包含比其他更多的字符。 - 现在总是搜索最大的行（开始时这将是最后一行），取出它的第一个单词并将其放在上一行的和处。重复直到第一行最长。
- 任何时候你都应该存储你的实际最大线宽
L，这样你就可以恢复L最小时的情况。
（改编自此处，
如果我们将单词长度视为数字列表，我们可以对分区进行二分查找。
我们的 max length 范围从 0 到 sum (word-length list) + (num words - 1), meaning the spaces。 mid = (range / 2)。我们检查 mid 是否可以通过在 O(m) 时间内划分为 N 集合来实现：遍历列表，将 (word_length + 1) 添加到当前部分，而当前总和小于或等于 mid。当总和通过mid时，开始新的部分。如果结果包含 N 或更少的部分，则 mid 是可以实现的。
如果可以达到mid，请尝试较低的范围；否则，更高的范围。时间复杂度为O(m log num_chars)。 （您还必须考虑如何删除每个部分的 space，这意味着换行符的位置，计算中的特征。）