Mic*_*zic 6 arrays string algorithm partitioning
假设我们有一个像这样的段落:
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 repreptderit 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行文本块.
这是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.
我们如何找到用换行符替换哪些空格字符以获得最少尝试的最窄(最长行上的字符数最少)？
假设文本由m个单词组成,我们将从1到m编号.将f(i,j)定义为子问题的最佳(最小宽度)解中任何一行的最大宽度(以字符为单位),该子问题仅由前i个单词组成,在使用正好j个换行符的限制下.然后,f(m,n)给出整个问题的最佳可能中断序列的宽度.使用动态编程可以相当有效地解决这个问题.
令字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-word前缀尝试以下内容:确定打破该k-word的最佳方法将前缀添加到j行(即使用j-1换行符),并将我们从中获得的最大宽度与将其余的ik字放在最后一行上的宽度进行比较.每个前缀为我们提供了不同的候选解决方案,因此我们可以选择其中最好的一个.
现在我们可以计算最佳宽度f(m,n),我们如何使用它来实际构建解？幸运的是,动态编程中有一种标准技术.最快的方法是在计算f(i,j)期间记录(实际上是a,因为通常可能存在多个最优解)k的值,其在前趋表pred [i] [j]中产生最小值.计算出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,这意味着它实际上只存储0(= q <= m)的计算值f(q,j-1)的size-(m + 1)数组就足够了.
(从这里改编,如何以最小化每个分区总和的最大值的方式对整数数组进行分区？)
如果我们将单词长度视为数字列表,我们可以二进制搜索分区.
我们的max length范围是从0到sum (word-length list) + (num words - 1), meaning the spaces.mid = (range / 2).我们检查是否mid可以通过及时划分成N集来实现O(m):遍历列表,(word_length + 1)在当前总和小于或等于时添加到当前部分mid.总和过后mid,开始新的部分.如果结果包括N或少于部分,mid则是可实现的.
如果mid可以实现,尝试较低的范围; 否则,更高的范围.时间的复杂性是O(m log num_chars).(您还必须考虑如何删除每个零件的空间,意味着换行的位置,计算中的特征.)