最少回文分解动态规划

看到最长回文就先切下来，会不会使最后的块数最少？aaba 已足够否定这个想法。先取最长回文前缀 aa，余下 ba 要拆成两块，共三块；保留另一种开头 a，却能接上 aba，总共两块。为了比较这样的选择，需要记住不同前缀的最优结果。

形式陈述

问题、状态与递推

给定字符串 $s$ ，把它分解成若干连续、非空回文，要求连接后恰为 $s$ ，并最小化块数。令 dp[i] 是前缀 $s[0:i]$ 的最少块数；空前缀 dp[0]=0。对 $1\le i\le n$ ，

\boxed{\operatorname{dp}[i]=1+\min_{0\le j<i,\ s[j:i]\text{ 回文}}\operatorname{dp}[j].}

单字符总是回文，因此每个非空状态至少有候选 $j=i-1$ ，答案有限。依赖只指向更短前缀，按 $i=1,\ldots,n$ 递增计算就是合法的动态规划顺序。

previous[i] 保存使最优值成立的切点 $j$ 。本页从小到大枚举 $j$ ，仅在严格变好时替换，因此平局时选最小的末块起点，也就是较长的最后一块。这个约定保证输出确定，但不声称它会给出全体分块序列的字典序最小者。

常数时间回文判定与完整重建

先用Manacher 算法求 odd、even，再按中心查半径。下面的 manacher 函数由该页提供，完整下载脚本包含所有定义，可独立运行。

python

def is_palindrome(left, right, odd, even):
    n = len(odd)
    if not 0 <= left <= right <= n:
        raise ValueError('invalid half-open interval')
    length = right - left
    if length == 0:
        return True
    center = (left + right) // 2
    return (odd[center] >= length // 2 + 1 if length % 2
            else even[center] >= length // 2)


def minimum_palindrome_factorization(s):
    odd, even = manacher(s)
    n = len(s)
    dp, previous = [0] + [n + 1] * n, [-1] * (n + 1)
    for end in range(1, n + 1):
        for start in range(end):
            if is_palindrome(start, end, odd, even) and dp[start] + 1 < dp[end]:
                dp[end] = dp[start] + 1
                previous[end] = start
    intervals = []
    end = n
    while end:
        start = previous[end]
        intervals.append((start, end))
        end = start
    intervals.reverse()
    return dp, previous, intervals

函数同时返回数值表、前驱表与半开区间列表。空输入返回 dp=[0]、previous=[-1]、空分块列表。非空字符串若最少 $k$ 块，内部切口数为 $k-1$ ；空串切口数约定为零，不能一律用 dp[n]−1 得到负一。

直觉

最后一块把一个解切成两个独立部分

任何合法分解都有最后一块 $s[j:i]$ ，它必须回文。前面各块恰覆盖 $s[0:j]$ ；如果它们不是该前缀的最少分解，换成更优前缀方案不会改变最后一块，便能改进整个分解。因此最优方案必出现在递推的某个候选中。

反过来，每个候选都由一个已经可行的前缀分解与一个真实回文末块拼成，不会产生重叠、空块或遗漏字符。前一段保证“不漏最优”，这一段保证“不接纳非法解”；二者合起来才证明等号。

也可以把边界 $0,1,\ldots,n$ 当作有向无环图的顶点。每个回文区间 $[j,i)$ 给一条代价一的边 $j\to i$ 。从零走到 $n$ 的路径与回文分解一一对应，dp 就是在按顶点顺序求最短路径。最长回文只是其中一条跨度较大的边；跨度大不保证它位于最短路径上。

前驱证书验证可行性，递推表验证最优性

从 n 沿 previous 倒走，每次严格减小前缀长度，最终到零，故重建不会成环。所得每一段都经回文判定，连接顺序恢复后覆盖全文，这给出可行性证书。

仅展示三段回文只能证明“至多三块”，不能证明“不可能两块”。若要独立核验最优性，还须检查每个 dp[i] 满足全部合法转移的最小值，或用另一份穷举切点程序对小实例确认。代码同时返回 dp 与 previous，正是为了把数值最优与具体输出两部分都交出来。

例子与边界

把主例的每个前缀真正算完

对 abacdcabba，结果为：

前缀长度 $i$	0	1	2	3	4	5	6	7	8	9	10
dp[i]	0	1	2	1	2	3	2	3	2	3	3
previous[i]	−1	0	1	0	3	4	3	2	1	8	6

长度六时，回文末块有 c 和 cdc。取单字符得到 dp[5]+1=4；取 cdc 得 dp[3]+1=2，所以前六字符拆成 aba|cdc。长度八时，长七的 bacdcab 与前面的单字符 a 组成两块，故 dp[8] 从上一前缀的三降到二。最少块数不必随前缀增长单调递增。

长度十时，所有非空回文后缀只有 a 与 abba。前者代价 dp[9]+1=4，后者代价 dp[6]+1=3，选切点六。倒走 $10\to6\to3\to0$ ，输出 $[0,3),[3,6),[6,10)$ ，即 aba|cdc|abba。最后一步穷尽两个末块，再结合前缀最优值，才完成三块最优的证明。

最少块数不能代替恰好 k 块判断

aba 最少一块，可以拆成三个单字符，却不能拆成恰好两块：两个可能切点分别留下 a|ba、ab|a，都含非回文块。所以“最少块数≤k≤n”不是恰好 k 块可行的充分条件。

若要回答恰好 k 块，应额外记录块数维度的可达性，或分别维护奇偶块数的最小值并证明可细分性质。若每块有不同费用，递推中的常数一也必须改成该区间的费用；费用读取和计算成本随之进入复杂度。不要在不改变状态或转移的情况下把本页接口扩张为任意分块任务。

推论与应用

线性预处理仍留下二次方条候选边

两层循环一共检查 $1+2+\cdots+n=n(n+1)/2$ 个区间。每次判定与整数状态操作按机器字常数成本计，所以总时间 $O(n^2)$ ，数组、前驱与输出区间合计 $O(n)$ 空间。这里避免了存一张 $n\times n$ 的回文真假表，但并未减少候选切点数量。

回文树给另一种执行方法：追加到位置 i 后，从 last 沿回文后缀链接走，对每个节点 v 检查 dp[i−len[v]]+1。这样只枚举真的回文末块，不再逐个拒绝非回文区间；主例共检查十六次，而非五十五次。链接按长度递减走，对应起点递增，能保持上面相同的平局规则。

然而 $a^n$ 每个前缀的所有后缀都回文，链接枚举仍需 $n(n+1)/2$ 次。回文树构建的线性摊还界只覆盖“找最长与次长后缀”的搜索，不覆盖这轮主动枚举全部后缀的 DP。更快的算法还须把等间距后缀分组并复用组内最小值；原论文的 $O(n\log n)$ 方法另有结构与跨前缀缓存证明。[1, §3–4][2, §4] 本页两份实现都明确保留二次方最坏界，不把换了数据结构当作已经获得这种加速。

$O(n\log n)$ 也不是这个问题已知算法的终点：Borozdin 等在2017年给出了使用 $\Theta(\log n)$ 位机器字的单位成本 Word-RAM 线性时间在线算法。[3] 那需要分组、预测和批量位运算的进一步组织，不能由本页的普通循环直接推出。

单元终结任务：交付一份回文分析记录

输入 abacdcabba，提交下面五件可以互相校验的结果：

两份半径数组，并用中心四与间隙八各复算一次扩张
十六次出现的总数，以及十种不同内容的列表；说明两者为什么不同
回文树 last 的十步轨迹，画清 bb→abba 扩展边与 abba→a 后缀链接
各内容出现次数，特别核对 a:4,b:3,c:2,d:1；节点计数和应为十六
完整 dp/previous 表，重建 aba|cdc|abba，用末块候选证明三块最优

迁移到上一单元的循环日志 bbaabbaabbaa 时，不改变字符顺序，也不先做循环规范化。它有三十次回文出现、十二种不同回文，最少两块，可取 bb|aabbaabbaa。这里最少分解针对原来的线性切口；把文本旋转后可能改变可用分块，不能因为两条日志属于同一循环类就复用原切点。

下载程序用逐区间反转独立核对半径与节点计数；短串再穷举全部内部切点集合，比较最少块数，并对照半径版和后缀链接版的完整前驱表。测试覆盖同一内容多次出现、回文跨越拟切点、空串与 Unicode 输入；这比只在主例上得到数值三更能检验整个接口。

参考资料

[1] Gabriele Fici, Travis Gagie, Juha Kärkkäinen and Dominik Kempa, A Subquadratic Algorithm for Minimum Palindromic Factorization, arXiv:1403.2431v2, 2014，§2：前缀动态规划与二次方基线；§3–4：回文后缀分组及更快最小值维护。
[2] Mikhail Rubinchik and Arseny M. Shur, EERTREE: An Efficient Data Structure for Processing Palindromes in Strings, arXiv:1506.04862v2, 2015，§4：回文分解、奇偶块数与 series links。本文只实现普通后缀链枚举，不宣称实现其中的 series-link 加速。
MIT 6.006, Lecture 16: Dynamic Programming Subproblems, 2020：先定义状态含义，再证明递推、顺序与解重建。
[3] Kirill Borozdin, Dmitry Kosolobov, Mikhail Rubinchik and Arseny M. Shur, Palindromic Length in Linear Time, CPM 2017, pp. 23:1–23:12，Theorem1及§1.1计算模型。这里只说明已知上界，不宣称实现该算法。

形式陈述 ​

问题、状态与递推 ​

常数时间回文判定与完整重建 ​

最后一块把一个解切成两个独立部分 ​

前驱证书验证可行性，递推表验证最优性 ​

把主例的每个前缀真正算完 ​

最少块数不能代替恰好 k 块判断 ​

线性预处理仍留下二次方条候选边 ​

单元终结任务：交付一份回文分析记录 ​

反向链接