P3625划分成回文串 | |
|
问题描述
给一个字符串, 要求把它分割成若干个子串,使得每个子串都是回文串。问最少可以分割成多少个。
例如:
“racecar”本身就是回文串,答案为1
“fastcar”,答案为7,分成的7个回文串为"f", "a", "s", "t", "c", "a", "r"
“aaadbccb”,答案为3,分成的3个回文串为"aaa", "d", "bccb"
输入格式
一行,一个由小写字母构成的字符串,该字符串的长度不超过2000
输出格式
一行,一个整数,表示最少分割出的回文串的个数。
样例输入
样例输入1:
racecar
样例输入2:
fastcar
样例输入3:
aaadbccb
样例输出
样例输出1:
1
样例输出2:
7
样例输出3:
3
来源 uva11584