动态规划与文本排版

FreeType是一款非常优秀的字体渲染库，Android和iOS当中都有使用。FreeType的官方网站上提供了两种不同的许可证供人们使用。一种是GPLv2，最常见的自由软件许可协议；另一种则是被称作FTL的许可证，是由FreeType的开发人员自己撰写的。前者自然是原封不动地取自自由软件基金会主席理查德·斯托曼（Richard Stallman）于1991年6月所写的文档，它的前面几段如图1所示。

命令行环境下的很多文字编辑器里，一行最多只能显示80个字符。因此，这篇文档每过几个词就会有一处换行，以保证每行都不超过80个字符，从而能够顺畅地在这些文字编辑器里展示出来。有趣的是，FreeType自家的FTL许可证虽然也是纯文本格式，虽然也在用换行来控制文档页的宽度，但看起来效果却完全不一样（如图2所示）。

为什么FTL文档看起来要漂亮得多呢？仔细观察就会发现端倪：GPLv2文档的右边界参差不齐，而FTL文档的左右两端都是对齐了的。你或许会感到万分诧异：这怎么可能做得到呢？难道作者遣词造句的功力如此之强，让FTL文档的各行恰好拥有完全相同的字符数？当然不是。再仔细观察，你就会注意到，在FTL文档中，相邻单词之间的间隙时大时小，有的地方只有1个空格，有的地方则有2个甚至更多的空格。借助这个小技巧，便能让文档的右端平正整齐，如信纸上工整的字迹一般，令人赏心悦目。

但是，如果有哪一行要添加大量额外的空格才能撑到所需的宽度，这一行就会因为过于稀疏而变得突兀，文档美化计划也将会因为这点瑕疵而泡汤。因此，究竟在什么地方换行，就变得非常讲究了。其中一种最容易想到的策略就是，每次总是把当前行尽可能填满后再换行。联想到上一节讲过的内容，你会发现，这其实就是一种简单的贪心策略。但是这一回，我们就没有那么幸运了——在这个问题中，利用贪心策略得到的结果并不总是最优的。假设我们有如下英文句子：

“i18n” is an abbreviation, where “18” refers to the 18 characters deleted in “internationalization”.

并且文档的页面宽度限定在每行32个字符。从“i18n”到“where”正好32个字符，刚好能放进一行里；从“18”到“characters”正好又是32个字符，恰巧又能凑成一行。但最后面的“internationalization”这个词太长了，以至于剩下的这些单词没法挤到一行里去，必须要再换一行。结果，第二行空空如也，甚是别扭。一个更聪明的做法则是把“where”一词挪到下一行去，把“18 characters”挪到再下一行去，这样匀一下之后，看起来就会好很多（如图3所示）。这充分地说明了，贪心策略得到的结果并不总是最优的。

所以，我们的问题就是，怎样才能找到一种最优的换行方案。等等，在此之前我们还要解决一个更基本的问题：怎样的方案才算最优的。能不能规定，每添加一个额外的空格就罚1分，而最优的换行方案则是总罚分最小的方案？显然不行。图3所示的两种合法方案中，添加的额外空格都是22个，罚分都是22分，但后者仍然比前者看起来更舒服。究其原因，并不是因为额外空格的总数更少，而是因为它们更均匀地分布在了各行。因此，我们不但希望换行方案的罚分会随着额外空格数的增加而增加，还希望在各行的额外空格数目之和相同的情况下，这些数目之间的差值越大，带来的罚分也就越多。实现这一点的其中一种方法就是，让各行的罚分随着该行额外空格数的增加而加速增加，比如规定每一行的罚分都等于该行所需的额外空格数的平方。这意味着，如果某一行的额外空格数从3增加到4，该行的罚分会从9增加到16，共增加了7分；但若这一行的额外空格数从8增加到9，该行的罚分会从64增加到81，足足要增加17分。于是，在额外空格本来就很多的行里继续增加几个额外的空格，同时在额外空格本来就少一些的行里减去同样多个额外的空格，那么增加的罚分会比减少的罚分更多——这说明，即使总的额外空格数量不变，各行的额外空格数目变得更加悬殊，也会导致总罚分的增加。这种罚分体系非常符合我们的需要：既能反映出额外空格总数的多少，也能反映出额外空格数的分布情况。因而我们正式定义，在一个换行方案当中，每一行的罚分就是该行所需的额外空格数的平方，而最优的换行方案则是总罚分最小的方案。

图3所示的两种合法方案中，前者各行的额外空格数依次是0、0、22、0，它们的罚分依次为0、0、484、0，总罚分就是484。后者各行的额外空格数依次是6、8、8、0，它们的罚分依次是36、64、64、0，总罚分就是164。我们直觉上认为更好的方案，总罚分果然也要小一些。那么，这是否就是总罚分最小的换行方案呢？我们自然可以枚举所有可能的换行方案，但这样做的效率太低了。为了得到一种快速生成最优换行方案的算法，我们还需要再多动动脑子。

在观察图3时，你或许已意识到，由于前后两种合法的方案中，最后一行都是由“internationalization”独占的，因而两种方案究竟孰优孰劣，完全取决于前面13个单词的换行方案。当然，这13个单词的换行方案远不止这么两种，究竟哪一种方案最好，又要取决于它们的最后一行里有哪些单词。这有6种不同的情况（如图4所示），它们的罚分从1分到900分不等，但每种情况下的总罚分究竟能有多小，还得取决于每种情况下更前面的那些单词的最优换行方案。例如，第2种情况下的最小总罚分，就应该等于s(11)+484，其中s(11)就表示单词“deleted”之前的11个单词的最小总罚分。

在某个最优化问题中，如果整个问题的最优解需要不断依赖于前面的子问题的最优解，我们就说这个问题具有“最优子结构”（optimal substructure）。当然，不是所有最优化问题都具有最优子结构。如果我们在做的不是让换行方案的总罚分最小，而是让换行方案的总罚分最接近整百数，那么这个问题就不再具有最优子结构了——前面的单词获得的总罚分更接近整百数，整个换行方案的总罚分不见得更接近整百数。

别忘了，整个段落的最后一行不见得是由最后一个单词独占的，也有可能是由最后两个单词组成的，而且这种大情况也有它自己的一系列子问题（如图5所示）。究竟在这两种大的情况中，哪一种会通向真正的最优解，我们事先是不知道的。因此，我们需要把这两种大的情况都考虑到。我们需要考察每一种大情况里的所有子问题，进而要去考察所有子问题的子问题，等等，直到这些子问题足够简单为止。

目前，这一切看上去似乎都与刚才的枚举策略没什么两样，然而只需要注意到下面这一点，一个高效算法的轮廓就慢慢浮现出来了：在问题分解的过程中，所得的子问题会有大量的重复。在图5中，为了获得第一种情况的最小总罚分，我们需要知道单词“deleted”前的那11个单词的最小总罚分，而这其实就是s(11)，刚才在图4中就已经涉及了。如果一个最优化问题当中，不同子问题的子问题有可能是同一个问题，我们就说这个最优化问题具有“重叠子问题”（overlapping subproblem）。同一个子问题会涉及很多次，但我们只需要计算一遍就行了，这会大大地节省运算的时间。

既然这样，我们为何不从最底层的子问题出发，先算出它们的最优解，再以此为基础算出更高一层的子问题的解，并不断这样做下去，直到算出整个问题的最优解？也就是说，我们可以先求出s(1)，再借助s(1)的值求出s(2)，再借助s(1)和s(2)的值求出s(3)，等等，直到我们求出s(14)，这也就是整个问题的答案了。为了叙述简便，我们下面用cost(i..j)表示把第i个单词到第j个单词放到一行中去的罚分。需要注意的是，如果这些单词太长，根本没法挤到一行中去，则罚分应为无穷大；如果第j个单词正好是整个段落的最后一个单词（并且这些单词确实能放入一行），则罚分为0。另外，我们规定s(0)=0，表明初始时总的罚分为0。显然，s(1)就等于s(0)+cost(1..1)，s(2)的值就等于s(0)+cost(1..2)和s(1)+cost(2..2)的最小值，s(3)的值就等于s(0)+cost(1..3)、s(1)+cost(2..3)、s(2)+cost(3..3)的最小值……总之，s(i)就等于s(k)+cost(k+1..i)的最小值，其中k可以取一切小于i的非负整数。我们需要特别记录一下，每次都是哪个k让s(i)取到了最小值，这样才能追溯出最小总罚分的来历，得到它所对应的具体换行方案。

图6以计算s(1)、s(2)、s(3)和s(13)为例，展示了动态规划的过程。在求每一个s(i)的过程中，我们都试着把这部分单词中的最后1个单词、最后2个单词、最后3个单词等放入最后一行，直到最后一行放不下更多的单词（或者说罚分将会达到无穷大）为止。计算每种情况下的最小罚分时，完全不用关心更前面的那些词的最优换行方案是什么，可以直接参考前面已经求过的s(1), s(2), …, s(i-1)值，优胜情况一比就知道，s(i)的值也就出来了。我们总是用两行圆点来代表更前面的那些词的最优换行方案（即使它们并不占两行）。

对我们的例子进行处理后，可以得到，s(1)到s(14)的值分别是676,529,400,36,0,464,261,180,100,61,0,221,164,164，所对应的最优的k分别是0,0,0,0,0,3,4,4,4,4,5,9,9,13。因此，图3最后给出的换行方案真的是最好的方案。

对于所有具有最优子结构和重叠子问题的最优化问题，上面的技巧都是有效的。我们不再是把问题当作一个有机的整体来看待的，而是把它拆成了一层一层的子问题，然后就像搭积木一样，不断计算局部的最优决策，最终自底向上地推出全局的最优决策。1954年，美国数学家理查德·贝尔曼（Richard Bellman）在一篇论文中专门谈到了这种解决问题的技巧。他用“动态规划”（dynamic programming）一词来指代这种思想，这个词语一直沿用至今。

从FreeType到动态规划，所有这一切都有一个最基本的前提：假设每个字符所占的宽度是相同的。日常生活中的文本排版显得更加灵活，各种字符所占的宽度更贴近书写和阅读习惯，比如字母i和l较窄，字母w和m较宽等。刚才的算法几乎可以立即扩展到这种情况当中，我们需要做的，仅仅是把各种字符的宽度信息纳入罚分公式中去即可。

在中文的世界里，换行问题同样存在。你知道出一本书最让人头疼的事情是什么吗？对于我来说，最让人头疼的恐怕要算后期的排版了。为了让不该折行的地方不发生折行，我和排版人员必须经过无数次的沟通。在我写《思考的乐趣：Matrix67数学笔记》一书的时候，遇到过的最麻烦的段落要算第3章中的《万能的连杆系统》了。那篇文章中有一段是这样的：

在这短短的一百来字里，有很多成分必须要在一行内显示，绝对不能在中间掐断，例如“AB·AE”、“△ABM”等。另外，“E点”、“圆O”等情况最好也不要被拆成两行，不然对阅读体验的影响很大。还有一点：标点符号是绝对不能出现在行首的。这意味着，最后面那个“直线”的“线”及其后的句号必须在同一行内，中间那个“AM·AN=AB·AE”连同后面的逗号也应被视为不可分割的整体。最麻烦的情况就是：某个不能折断的成分既可上又可下，但是放在上一行末尾会让上一行特别挤，放在下一行又会让上一行特别空。而且，调整过程经常是牵一发而动全身，等到这个地方终于改好了的时候，后面的东西又全部乱套了。这种时候，换行问题的处理方法就派上用场了。

还有一个出人意料的排版问题，最终也会归结为我们的换行问题。在给书进行排版时，我们往往希望每个段落都能完整地显示在一页上，最好不要拆成两页。而段落末行跑到下一页的页首，或者段落首行正好在前一页的页尾，则更是排版中的大忌。另外，每一页上的脚注也必须和被注解的内容在同一页里，如果某个脚注恰好很长，就会出现这种让人哭笑不得的局面：把脚注放到第3页，被注解的内容就会被挤到第4页去；但把脚注放到第4页去，被注解的内容就会重新回到第3页。每一页究竟显示多少内容，究竟在哪些地方分页，也成为了排版中的一个难题。不难发现，分页问题其实就是更大尺度上的换行问题，可以直接套用换行问题的解决办法，反正问题的本质是完全一样的。