| 问题描述 |
|---|
给出一个字符串$$s$$，求至少需要切割几次才能把$$s$$分为若干个回文串。 |
| 输入描述 |
一个仅包含小写字母且长度不超过$$5000$$的字符串。 |
| 输出描述 |
在一行中输出最少的切割次数。 |
| 样例输入复制样例 |
aab |
| 样例输出 |
1 |
| 提示说明 |
| 切成$$aa$$和$$b$$。 |
| 相关 |