第10章：文本换行布局——动态规划

一行能放几个词？数学上最小的代价，就是最均匀的排版。

10.1 问题：给定一段文本和行宽，如何断行

先把问题定义干净。我们有一个文本块：一串词 words[0..n-1]，每个词量好了宽度 word_widths[i]（说人话：量宽，也叫度量，就是用字体数据算出文字实际占多宽），外加行宽 page_width（说人话：一行能容纳多少宽度，超出就得换行）和词间距 space_width。要做的决定是：在哪些词之后换行。TextBlock::layout 的核心任务，就是算出这个断行方案——并让"每一行的右缘空白"尽量均匀。这不是嵌入式专属问题，它有个响亮的名字：word-wrap（说人话：在合适的位置把长文本切成多行，也就是"断行"，英文也叫 text justification），是每一个排版引擎都要过的关，从浏览器到 LaTeX 无一例外。

一个直观但次优的解法是贪心：从行首开始，能塞就塞，塞不下就换行。它快，但产出的行右缘参差。README 在 "Laying out a section of the book" 一节里提到了 MIT 公开课（20. Dynamic Programming II: Text Justification, Blackjack）和 geeksforgeeks 的 word-wrap DP 题（DP-19），正是因为这道题最适合用来演示"贪心 vs 动态规划"的分野——说人话：动态规划是一种算法思路，把大问题拆成一个个子问题、保存中间结果来复用，从而避免重复计算。README 原话："we measure the width of each word in the block and then use some dynamic programming to break the words up into lines"（先量每个词的宽度，再用动态规划把词切进多行）；并且它大方承认："I copied the solution for this problem from geeksforgeeks with minor modifications"（我照着 geeksforgeeks 抄了这份解，做了点小改动）。

为什么"均匀"必须用数学定义？因为"好看"没法直接比较。我们把目标量化成一句话：每一行右侧空白的平方和越小，排版越均匀（最后一行除外——书的末行不强制对齐，代价记 0）。这就是整个算法的代价函数。注意"平方"而不是"绝对值"：平方放大了大块空白，算法会宁可把空白分散成多个小块，也不肯容忍一行巨空、一行挤爆。第 1 章预告过的那份 dp[] 代码，正是这段代价函数的物化。

/* 换行问题的输入与输出（概念模型，非源码） */
输入：
  words[0..n-1]       // 一串词
  word_widths[i]      // 每个词的宽度（由 renderer 量出）
  page_width          // 一行可用宽度
  space_width         // 词与词之间的空隙宽度
输出：
  line_breaks[]       // 每个"行尾"之后下一个词的起始下标
目标：
  最小化 Σ (page_width - 行实际宽度)² ，最后一行例外（代价为 0）

/* Renderer.h：度量能力全部来自这五个虚函数 */
virtual int get_text_width(const char *text, bool bold = false, bool italic = false) = 0;
virtual int get_space_width() = 0;
virtual int get_page_width() = 0;
virtual int get_page_height() = 0;
virtual int get_line_height() = 0;

量	含义	来源
words[i]	第 i 个词	TextBlock::add_span 分词产生
word_widths[i]	第 i 个词的像素宽度	renderer->get_text_width
page_width	一行可用宽度	renderer->get_page_width（可被 max_width 覆盖）
space_width	词间距	renderer->get_space_width
line_height	行高（分页用）	renderer->get_line_height

10.2 动态规划：量词宽、代价函数、从后往前递推

先算一下朴素搜索的代价。把 n 个词切成若干行，断点组合是指数级的——n=50 就有天文数字种切法，绝不可能枚举。动态规划的核心洞察只有一句：从单词 i 开始的那一行，无论前面怎么断，最优后缀只取决于 i 自己。于是我们定义 dp[i] = 从单词 i 开头那一行起的"最小总代价"（本行的代价 + 之后所有行的代价），并让每个 i 都向前看一步，决定"这一行到哪个词为止最划算"。有了 dp[]，指数级搜索就塌缩成一张可以查表的小表。

递推怎么写？对每个 i，尝试把行从 i 一直延伸到 j（j ≥ i），累加 currlen（词宽之和 + 词间距）；一旦 currlen > page_width 说明塞不下了，break。可行时，这一整段的代价 = 当前行右侧空白的平方 (page_width - currlen)² + 之后所有行 dp[j+1]；若 j 恰好是最后一个词（最后一行），代价记 0。在所有候选 j 里取最小，写进 dp[i] 与 ans[i]。为了正确安放"最后一行"，递推必须从最后一个词开始、倒着往前算：dp[n-1]=0, ans[n-1]=n-1，然后 i 从 n-2 递减到 0。代码注释里还保留着 geeksforgeeks 原版的痕迹（"the last line cost is zero"）。

/* TextBlock.cpp：动态规划求最优断行（节选） */
int n = word_widths.size();
int dp[n];                    // dp[i]：从词 i 开始那行的最小总代价
size_t ans[n];                // ans[i]：最优时本行最后一个词的下标

dp[n - 1] = 0; ans[n - 1] = n - 1;
for (int i = n - 2; i >= 0; i--)
{
  int currlen = -1;
  dp[i] = INT_MAX;
  for (int j = i; j < n; j++)
  {
    currlen += word_widths[j] + space_width;   // 行 i..j 的累计宽度
    if (currlen > page_width) break;          // 塞不下了
    int cost = (j == n - 1)
        ? 0                                    // 最后一行代价 0
        : (page_width - currlen) * (page_width - currlen) + dp[j + 1];
    if (cost < dp[i]) { dp[i] = cost; ans[i] = j; }
  }
}

/* TextBlock.cpp：把 ans 表翻译成真正的换行点 */
size_t i = 0;
while (i < n)
{
  i = ans[i] + 1;                  // 跳到下一行的起始词
  if (i > n)
  {
    ESP_LOGI("TextBlock", "fallen off the end of the words");
    break;
  }
  line_breaks.push_back(i);          // 记下这一行"结束之后"的下标
  if (line_breaks.size() > 1000)  // 防御：一本书的行数不可能上万
  {
    ESP_LOGE("TextBlock", "too many line breaks");
    break;
  }
}

复杂度与直觉。先说算法复杂度（说人话：描述算法耗时随输入规模增大而变快多少的量，常用 O(...) 表示，如 O(n²) 意思是输入翻倍、耗时约翻四倍）：两层循环，i 和 j 都至多到 n，最坏 O(n²) 次比较；而一行通常只有十几个词，n 的规模很小，几十个词也就是几百次运算，在 ESP32 上毫无压力。ans[] 是个"前缀指引"：每个 i 记住最优情况下"这一行到哪结束"，回溯时像跳格子一样 i = ans[i] + 1，一步一行，得到的就是最优断行方案。这个"算的时候存决策、算完再回放"的两段式，是动态规划的标准动作——先正向填表，再反向走表。

量	含义
dp[i]	从词 i 开始的最小总代价（本行 + 后缀）
ans[i]	dp[i] 最优时，本行最后一个词的下标
currlen	试探"i..j 放进同一行"的累计宽度
cost	某种断法（i..j 成行）的总代价
line_breaks	回溯得到的"行尾后下标"集合

10.3 具体实现：TextBlock 如何度量与换行

度量在进入 DP 之前就完成了。TextBlock::layout 的第一段：for 每个词调一次 renderer->get_text_width(words[i], word_styles[i] & BOLD_SPAN, word_styles[i] & ITALIC_SPAN)，把结果 push 进 word_widths。粗细和斜体会改变字形宽度，所以度量必须带上样式位——这正是上一章 add_span 里每个词都存一份 word_styles 的原因：样式是逐词的，度量也是逐词的。第 9 章埋下的"逐词样式"，在这里第一次派上用场。

词从哪来？add_span 负责把一段文本切成词：它把 span 拷进自己的缓冲区，然后一遍 skip_whitespace（跳空白）加一遍 skip_word（吃到空白为止）反复扫描，把每个词的结束位置填上 '\0'，记下指向词头的指针，并用 (is_bold ? BOLD_SPAN : 0) | (is_italic ? ITALIC_SPAN : 0) 记录样式。空白定义只有三种字符：空格、'\r'、'\n'——代码开头的 TODO 注释也诚实写着：is there any more whitespace we should consider?（还有别的空白该考虑吗？）这是又一个"够用就好"的取舍，也正是给读者留下的改进钩子。

/* TextBlock.cpp：把一段文本切成词（节选） */
void TextBlock::add_span(const char *span, bool is_bold, bool is_italic)
{
  int length = strlen(span);
  char *text = new char[length + 1];
  strcpy(text, span);
  spans.push_back(text);                        // 拷一份，稍后要改

  int index = 0;
  while (index < length)
  {
    index = skip_whitespace(span, index, length);  // 跳过空白
    int word_start = index;
    index = skip_word(span, index, length);        // 吃到下一个空白
    int word_length = index - word_start;
    if (word_length > 0)
    {
      text[word_start + word_length] = '\0';     // 在词尾打结
      words.push_back(text + word_start);          // 记下词头指针
      word_styles.push_back((is_bold ? BOLD_SPAN : 0)
                          | (is_italic ? ITALIC_SPAN : 0));
    }
  }
}

/* TextBlock.cpp：layout 第一段 —— 逐词度量（进入 DP 前） */
void TextBlock::layout(Renderer *renderer, Epub *epub, int max_width)
{
  for (int i = 0; i < words.size(); i++)
  {
    int width = renderer->get_text_width(
        words[i], word_styles[i] & BOLD_SPAN, word_styles[i] & ITALIC_SPAN);
    word_widths.push_back(width);
  }
  int page_width  = max_width != -1 ? max_width : renderer->get_page_width();
  int space_width = renderer->get_space_width();
  /* …… 然后进入 10.2 的动态规划 …… */
}

max_width 参数是个彩蛋。layout(renderer, epub, int max_width = -1) 允许调用方覆盖行宽。默认 -1 表示"用整页宽"；而 EpubList.cpp 里渲染书目标题时传了 text_width（把标题限制在书名那一列的宽度内），EpubToc.cpp 渲染目录条目时传了 renderer->get_page_width()。同一个 TextBlock，既能排整段正文、也能排单行标题——行宽从"全局常量"变成"可注入参数"，靠的就是这个默认参数。它让"把块塞进多窄的一行"变成了调用方的自由，而不必改任何换行算法。

步骤	代码位置	做什么
度量词宽	layout 开头 for 循环	get_text_width 逐词量宽
决定行宽	max_width 覆盖 / get_page_width	支持单行标题等窄行场景
DP 断行	双层 for	dp / ans 求最优断点
回溯	while 循环	生成 line_breaks
定位 x	逐行 for	计算每个词的 word_xpos

10.4 对齐：JUSTIFIED / CENTER / LEFT，以及局限与改进

换行之后还有对齐这一关。TextBlock 的 BLOCK_STYLE 有四个值：JUSTIFIED（两端对齐，正文默认）、LEFT_ALIGN、CENTER_ALIGN（标题）、RIGHT_ALIGN。layout 后半段遍历每一行：先算 spare_space = page_width - total_word_width（本行剩余空白），再决定把空白塞到哪。两端对齐的做法是把多余空白均摊到词与词之间——actual_spacing = spare_space / (number_words - 1)，即拉大词间距填满整行；但最后一行不摊（i != line_breaks.size()-1 才摊），免得末行被拉得稀稀拉拉。居中则是把整行空白的一半留给左缘：xpos = (spare_space - (number_words-1)*space_width) / 2。

/* TextBlock.cpp：逐行定位词的 x 坐标（节选） */
float spare_space = page_width - total_word_width;
float actual_spacing = space_width;
int number_words = line_breaks[i] - start_word;
/* 两端对齐：非末行、且一行有多个词时，把剩余空白均摊成词间距 */
if (i != line_breaks.size() - 1 && style == JUSTIFIED)
{
  if (number_words > 1)
    actual_spacing = spare_space / float(number_words - 1);
}
float xpos = 0;
if (style == RIGHT_ALIGN)
  xpos = spare_space - (number_words - 1) * space_width;
if (style == CENTER_ALIGN)
  xpos = (spare_space - (number_words - 1) * space_width) / 2;
for (int word_index = start_word; word_index < line_breaks[i]; word_index++)
{
  word_xpos[word_index] = xpos;
  xpos += word_widths[word_index] + actual_spacing;
}

这一段的产物是 word_xpos——每个词的 x 坐标。README 渲染一节里有一句很得意的话："a side effect of the text justification and line-breaking is that we have already computed the x position of each word on a line"（两端对齐和断行的一个副作用是，每行里每个词的 x 坐标都已经算好了）。渲染时 TextBlock::render 只需逐词 draw_text(x_pos + word_xpos[i], y_pos, ...)，不必二次排版。布局期算好的坐标，渲染期直接消费——这一分工，让"按一下键翻一页"的实时性有了保证，也是"先把整页内容算好、最后才 flush"这套电纸屏编程模型的局部缩影。

/* TextBlock.cpp：渲染 —— 布局期坐标直接消费 */
void TextBlock::render(Renderer *renderer, int line_break_index, int x_pos, int y_pos)
{
  int start = line_break_index == 0 ? 0 : line_breaks[line_break_index - 1];
  int end = line_breaks[line_break_index];
  for (int i = start; i < end; i++)
  {
    uint8_t style = word_styles[i];
    renderer->draw_text(x_pos + word_xpos[i], y_pos, words[i],
                        style & BOLD_SPAN, style & ITALIC_SPAN);
  }
}

局限也要承认。README 的 "How well does it work" 一节直言："The code makes no attempt to break pages at suitable places - there are hints that can be extracted from the XHTML files and there are also CSS files that could be used"（代码完全没有尝试在合适的地方分页——XHTML 里有可提取的线索，还有可用的 CSS）。换行本身也是如此：Renderer.h 里定义了 MAX_WORD_LENGTH 100，但 add_span 的分词只认空白、并没有真正按这个上限截断超长词；连字符断词（hyphenation）完全没有；词宽用的是单一字形序列，没有 kerning；空白只认三种字符。这些都是"够用"与"精致"之间的差距，也是 README 说它能 "be improved considerably"（大幅改进）的原因。

环节	现状	改进空间
断行	O(n²) 动态规划，逐行代价平方	Knuth–Plass 按行分段、限制每行词数上限
对齐	仅把空白均摊到单词间	支持逐字母对齐、避免连续出现大间距空行
断词	不处理超长词（MAX_WORD_LENGTH 未真正生效）	实现连字符断词、按行宽主动折行
度量	每个词调用一次 get_text_width	字形宽度缓存、加入 kerning
分页	y 超出页高即换页	用 XHTML/CSS 提示避免孤行孤字（见第 11 章）