解题思路
本题是典型的“划分型动态规划”。设字符串为 s[0..n-1]，我们用一维 DP 求解最少段数：
-
定义 dp[i]：表示将前 i 个字符（即子串 s[0..i-1]）切分成回文子串所需的最少段数。
-
初始条件：dp[0] = 0（空串不需要切分），其余 dp[i] 初始化为一个足够大的数（如 n）。
-
状态转移：枚举最后一段的起点 t（0 ≤ t ≤ i-1），若 s[t..i-1] 为回文，则
P3996.最少回文字符串分割
题面描述
给定一个只包含小写字母的字符串 s（长度为 n）。请将 s 切分成若干个非空且连续的子串，使得每个子串都是回文串，并使切分得到的子串个数最少。输出这个最少个数。
输入输出
输入：
一行一个字符串 s。
输出：
一行输出一个整数，表示将 s 分割成回文串所需的最少子串个数。
数据范围
- 1≤n=∣s∣≤400
- 字符均为小写字母
样例
输入
aab
输出
2
说明
最优切分为 aa|b，共 2 段。
输入
abacdc
输出
2
说明
最优切分为 aba|cdc。
开通会员即可查看完整视频题解： 1.题目讲解 2.思路分析 3.逐行代码手写
