回文串划分
有一个字符串S&＃xff0c;求S最少可以被划分为多少个回文串。
例如&＃xff1a;abbaabaa&＃xff0c;有多种划分方式。
a|bb|aabaa - 3 个回文串
a|bb|a|aba|a - 5 个回文串
a|b|b|a|a|b|a|a - 8 个回文串
其中第1种划分方式的划分数量最少。
Input输入字符串S(S的长度<&＃61; 5000)。Output输出最少的划分数量。Sample Input
abbaabaa
Sample Output
3
字符串dp。O(n^2)枚举中心点&＃xff0c;向两边找相同字符&＃xff0c;状态转移方程&＃xff1a;dp[k]&＃61;min(dp[k],dp[j-1]&＃43;1)。
#include
#include
#include
#include<string.h>
#include
#include<string>
#include
京公网安备 11010802041100号