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

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

1 · 一个递推式：枚举「最后一段」

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

dp[t] = agg over s in [0, t)  combine( dp[s], segCost(s, t−1) )

填完 dp[]，沿记录的「最优起点」回溯，就还原出每一段的边界。两个场景只是换 segCost（段代价）与 agg（聚合）——相册是 Σ 段代价最小、段数不限；分栏是 max 段和最小、恰好切成 K 段。

2 · 场景一：相册 justified layout

Flickr / Google Photos 那种相册：每行图片等高、右边缘对齐。一行装第 s+1..t 张图时，把它们按各自宽高比缩放到共同高度铺满容器宽度——图越多、越宽，共同高度就越矮。一行的代价 = 这个共同高度偏离目标行高的程度的平方 $((h - targetH) / targetH)^2$；越贴近目标越好。总代价 = 各行代价之和，用最优分段最小化它。末行按真实相册的做法处理：只要在目标高度下排得下，就左对齐、保持目标高度、不拉伸也不计代价（排不下时才当满行）。拖目标行高滑块或换图组，看两种排法即时重排：

贪心每行只顾把当前行填满就断行、不看后面，行高常偏离目标（有的偏扁、有的偏高），还容易让最后几张图形成孤行；DP 统筹全局，让各行都更贴近目标行高，末行也更自然。差距虽不总是量级之大——这正是相册库普遍用贪心的原因——但在混合宽高比、目标行高偏大时 DP 明显更整齐（内容分栏那节的 DP 优势更悬殊）。单步区的元素尺高亮的是当前 dp[t] 选中的「最后一行」。

3 · 场景二：内容分栏均衡

把 N 张不同高度的卡片按顺序分到 K 栏，让最高的那一栏尽量矮（整体最均衡，视觉不头重脚轻）。这是经典的 min-max 划分:dp[k][t] = 把前 t 项切成 k 栏时「最高栏」的最小值，枚举最后一栏 s+1..t，与前 $k-1$ 栏的最高栏取 max、再对 s 取 min。调 K 或换数据：

贪心「填至平均高度就换栏」，余量往往堆在末栏，最高栏明显高于理论最优；DP 全局权衡，最高栏更矮。注意 CSS 原生的 column-count 走的正是顺序填栏的贪心思路，所以偶尔会出现末栏偏空 / 偏满。

4 · 同一个模型，还能做什么

「枚举最后一段 + 段代价 + 回溯」这套骨架适用面很广。最著名的一例是段落断行(Knuth–Plass)：把一段文字的单词切成若干行，段代价 = 行内空格被拉伸 / 压缩程度的立方 + 惩罚，最小化总代价——就是 TeX 的断行、以及 CSS text-wrap: pretty 想逼近的效果，和贪心逐行（浏览器默认）相比更少出现「河流」与末行孤字。它与本页相册 justified 是同一族的最小化问题，只是段代价换成了排版的 badness。