Problem1090--最少回文串分割

1090: 最少回文串分割

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 167  Solved: 90
[Submit] [Status] [Web Board] [Creator:]

Description

PIPI听说同学们最近学习了回文串算法，现在它想考考你~
PIPI给你一个只含小写字母的字符串，请你将这个字符串拆分成几段，要求每段都是回文串，同时要求段数尽可能少。
racecar本身为回文串，故答案为1
fastcar只能拆成'f','a','s','t','c','a','t',答案为7
aaabcac可以拆成'aaa','b','cac'，答案为3

Input

多组输入
第一行为一个字符串，长度不超过1000

Output

输出拆分的最小段数

Sample Input 

racecar
fastcar
aaadbccb

Sample Output 

1
7
3

Source/Category

中等 动态规划 
[Submit] [Status]