解题思路

本题是典型的“划分型动态规划”。设字符串为 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] 为回文，则

题面描述

给定一个只包含小写字母的字符串 $s$（长度为 $n$）。请将 $s$ 切分成若干个非空且连续的子串，使得每个子串都是回文串，并使切分得到的子串个数最少。输出这个最少个数。

输入输出

输入： 一行一个字符串 $s$。

输出： 一行输出一个整数，表示将 $s$ 分割成回文串所需的最少子串个数。

数据范围

• $1 \le n=|s| \le 400$
• 字符均为小写字母

样例

输入

aab

输出

2

说明 最优切分为 aa|b，共 2 段。

输入

abacdc

输出

2

说明 最优切分为 aba|cdc。