51nod 1154

有一个字符串S,求S最少可以被划分为多少个回文串。
例如:abbaabaa,有多种划分方式。
a|bb|aabaa – 3 个回文串
a|bb|a|aba|a – 5 个回文串
a|b|b|a|a|b|a|a – 8 个回文串
其中第1种划分方式的划分数量最少。
Input

Output

Input示例

Output示例

 

dp的时候不用用 右端点,枚举每个回文串中间一个或两个(回文串可以是奇数个也可以是偶数个),每次可以更新右端点的dp值

 

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注