有一个字符串S，求S最少可以被划分为多少个回文串。
例如：abbaabaa，有多种划分方式。
a|bb|aabaa - 3 个回文串
a|bb|a|aba|a - 5 个回文串
a|b|b|a|a|b|a|a - 8 个回文串
其中第1种划分方式的划分数量最少。
Input
输入字符串S(S的长度<= 5000)。
Output
输出最少的划分数量。
Input示例
abbaabaa
Output示例
3
#include <cstring>
#include <iostream>
using namespace std;
const int MAXLEN = 5001;
char input[MAXLEN];
int l[MAXLEN];
int dp[MAXLEN];
bool isPalindrome(int a, int b)
{
while (a < b)
{
if (input[a] != input[b])
{
return false;
}
a++;
b--;
}
return true;
}
int main()
{
cin >> input;
int n = strlen(input);
l[0] = -1;
l[1] = 0;
dp[0] = 0;
dp[1] = 1;
int result = 1;
for (int i = 1; i < n; i++)
{
dp[i+1] = dp[i] + 1;
l[i+1] = i;
int temp = l[i] - 1;
if (temp >= 0 && input[i] == input[temp])
{
dp[i+1] = min(dp[i+1], dp[temp] + 1);
l[i+1] = temp;
}
for (int j = l[i]; j < i; j++)
{
if (isPalindrome(j, i))
{
l[i+1] = min(l[i+1], j);
dp[i+1] = min(dp[i+1], dp[j] + 1);
}
}
}
cout << dp[n] << endl;
return 0;
}
