题解

核心算法

从当前位置枚举下一段终点，仅当该段回文时继续递归。

思路推导

每组切点唯一决定一种分割，递归按切点从左到右枚举。

正确性说明

按照上述状态含义与转移顺序，每一步只使用已经正确求出的子问题；所有合法情况被完整计入，且互斥分类不会重复计数，因此最终输出即为题目所求。

复杂度

• 时间复杂度：O(2^n\cdot n)
• 空间复杂度：O(n)

易错点

回文区间右端点与 substring 长度容易写错。

完整标程见 std/main.cpp。