dp[t] = agg over s

最后一段的枚举：相册排版与内容分栏

一排元素按固定顺序排列——一行图片、一列卡片、一段文字的单词——要把它们切成若干连续段（每行放哪几张、每栏放哪几件、每行排哪几个词）。每种切法有一个代价，求代价最优的切法，就是最优分段 (optimal partition)。前端里的相册 justified layout 与内容分栏均衡都是它的实例，而工程里常见的贪心逐段只是局部最优。本页把两个场景都做成「贪心 vs DP」的对照。

1 · 最后一段的枚举

设 $dp[t]$ 是「最优地安排前 $t$ 个元素」的答案。要算它，只需枚举最后一段从哪里起——设它是第 $s+1 \dots t$ 个元素，那么前 $s$ 个的最优答案是子问题 $dp[s]$ ，再加上这一段自身的代价：

dp[t] = \operatorname*{agg}_{0 \le s < t}\ \operatorname{combine}\bigl(dp[s],\ \operatorname{segCost}(s,\, t-1)\bigr)

填完 $dp$ ，沿记录的「最优起点」回溯，就还原出每一段的边界。两个场景换的是段代价与聚合方式：相册要各段代价之和最小、段数不限；分栏要各段之和的最大值最小、且恰好切成 $K$ 段。

警示 · 这是同一套思路的两份实现，不是同一份代码换个参数。solveJustified 的状态是一维的 $dp[t]$ ，solveColumns 因为要约束「恰好 $K$ 段」而多一维，写成 $dp[k][t]$ ，两者在 core/partition.ts 里互不调用。把分栏说成「相册换个 segCost」会漏掉这一维。

2 · 相册 justified layout

Flickr 与 Google Photos 那种相册：每行图片等高、右边缘对齐。一行装第 $s+1 \dots t$ 张图时，把它们按各自宽高比缩放到共同高度铺满容器宽度——图越多、越宽，共同高度就越矮。一行的代价是这个共同高度偏离目标行高 $H$ 的相对量的平方，放大 100 倍后取整：

\operatorname{rowCost} = \operatorname{round}\Bigl(100\,\bigl((h - H) / H\bigr)^2\Bigr)

放大与取整都只是为了让读数好看，代价是偏离小于 0.5% 的行显示为 0，所以「总代价 0」并不等于零偏离。末行按真实相册的做法处理：只要在目标高度下排得下，就左对齐、保持目标高度、不拉伸也不计代价；排不下时才当满行算。

图 2-1 · 相册 justified layout 的贪心与 DP 对照。可拖目标行高滑块或切换图组，观察两种排法的行高偏离与末行处理；左侧贪心面板仅在严格劣于 DP 时变色。

贪心的失效模式与直觉不同。它只在自然宽度铺满容器时才断行，所以每个非末行都是被压扁的：三组预设 × 目标行高 60–180 步长 5 共 75 组实测，贪心的非末行没有一行高于目标（0/204），高于目标的全在 DP 那侧（85/234）——DP 允许行高在目标两侧摆动，换总偏离更小。默认视图（横竖混排、目标行高 100）里贪心的第二行 $h \approx 74$ 、代价 7，就是这样来的。

注 · 原先本节写的是「贪心容易让最后几张图形成孤行，DP 的末行更自然」，实测的方向正相反：末行只放一张图的比例是 DP 10/75、贪心 8/75，默认视图下贪心末行 3 张，而 DP 恰好甩出一张 $h \approx 575$ 的孤图。原因在末行免代价这条规则——把最后一张单独留给末行不花钱，DP 于是有动机这么做。改的是正文，不是引擎：这条规则本身是真实相册的做法。

DP 的优势也不是「常常差一个量级」。75 组里两者总代价完全持平的有 31 组（41%），贪心达到 DP 十倍以上的只有 6 组。差距最大的是「多宽图」预设在目标行高 135 处，31 比 1；「横竖混排」在 125–165 区间稳定拉开（125 时 14 比 3，160 时 21 比 7）。而「多宽图」在目标行高 ≥ 150 时两者逐点相等。相册库普遍用贪心，正是因为多数参数下这个差距并不存在。

3 · 内容分栏均衡

把 $N$ 张不同高度的卡片按顺序分到 $K$ 栏，让最高的那一栏尽量矮。这是经典的 min-max 划分： $dp[k][t]$ 是把前 $t$ 项切成 $k$ 栏时最高栏的最小值，枚举最后一栏 $s+1 \dots t$ ，与前 $k-1$ 栏的最高栏取 $\max$ ，再对 $s$ 取 $\min$ 。

图 3-1 · 内容分栏的贪心与 DP 对照。可调栏数 K 或切换数据，读数给出两者的最高栏高度；左侧贪心面板仅在严格劣于 DP 时变色。

贪心「填至平均高度就换栏」的余量落点也与直觉相反。它每灌满一栏都会略微超出平均值，超出的部分从后面的栏里扣，末栏因此普遍偏空：三组预设 × $K = 2 \dots 5$ 共 12 组实测，末栏无一例外是最矮或并列最矮的一栏，最高栏落在中前部。「错落卡片」 $K = 3$ 时贪心分成 14、17、8 三栏，最高栏是第二栏。

注 · 贪心还会用不满 $K$ 。greedyColumns 的换栏条件带 cols.length < K && i < N - 1，元素提前分完时就停手：实测「错落卡片」与「长短不一」在 $K = 5$ 时只产出 4 栏，「大件在中」在 $K = 4$ 时只产出 3 栏。页面左侧的栏数会与滑块上的 $K$ 对不上，这不是渲染错误。

12 组里 DP 严格胜出 7 组，最大差距是「错落卡片」 $K = 5$ 的 15 比 9；另外 5 组两者持平。把它与 §2 放在一起看，差距悬殊的是相册那一侧而非分栏。

浏览器的多栏布局并不走这个贪心。column-fill 的初始值是 balance，Chrome 151 实测三段等量内容分三栏得到的是 3 / 3 / 3 的均衡结果而非顺序灌满（核对于 2026-08）；顺序灌是 column-fill: auto。而且 min-max 分段另有一条最优算法——对最高栏高度二分，再用一次顺序灌做可行性检查， $O(N \log \sum h)$ ，比本页的 $O(K N^2)$ 更快 [2][3]。浏览器把栏排不匀，成因通常是不可断的内容与分栏片段化，不是算法次优。

4 · 同一骨架的其他去处

「枚举最后一段 + 段代价 + 回溯」这套骨架适用面很广。最著名的一例是段落断行 [1]：把一段文字的单词切成若干行，行的 badness 随行内空格的拉伸比增长（TeX 取三次方），再平方成 demerits 并叠加连字符等惩罚项，最小化全段总和。它与本页的相册 justified 是同一族最小化问题，只是段代价换成了排版的 badness。

CSS 的 text-wrap: pretty 想逼近的是同一个目标，但两家实现的进度并不同步（核对于 2026-08）：Chrome 117 起的实现只回看段末几行以避免孤字，不改善整段的右边缘参差；WebKit 在 2025 年的实现才是按 Knuth–Plass 做整段评估。「减少河流」不是这两者的目标，它只是拉伸量变小后的副产物。

建议 · 判断一个排版或布局需求是否值得上 DP，看它是不是「按顺序切成连续段、每段有代价、要全局最优」。是就套本页这套骨架，换段代价即换场景。若局部贪心已够好（多数瀑布流、普通换行），不必上 DP——§2 那 31 组持平就是这个判断的依据。

5 · 参考文献

Knuth, D. E., & Plass, M. F. (1981). Breaking paragraphs into lines. Software: Practice and Experience, 11(11), 1119–1184.
Bokhari, S. H. (1988). Partitioning problems in parallel, pipeline, and distributed computing. IEEE Transactions on Computers, 37(1), 48–57.
Han, Y., Narahari, B., & Choi, H.-A. (1992). Mapping a chain task to chained processors. Information Processing Letters, 44(3), 141–148.

🔗 相关链接

Minimum raggedness (Knuth–Plass) · Wikipedia 最优断行:把段落切成行使总 demerits 最小的 DP,与相册 justified 同族。TeX 断行与 text-wrap: pretty 的理论基础。
折行与断词 · 本站 · typesetting CSS 属性层的换行控制:white-space / overflow-wrap / word-break,以及 text-wrap: balance / pretty——断行 DP 在浏览器里的落地。
序列对齐 DP · 本站 · sequence-dp 另一族 DP:二维序列对齐 (LCS / 编辑距离 / DTW),与一维分段互为对照——都靠「子问题 + 回溯」。
背包问题九讲 · 本站 · dp 动态规划的思考艺术:状态、转移方程、循环方向,以及问法变化。分段 DP 的通用底层。