| |
|
试题描述
|
|
输入一个小写字母组成的字符串，你的任务是把它划分成尽量少的回文串。例如 racecar 本身就是一个回文串，fastcar只能分成7个单字母的回文串。aaadbccb最少分成3个回文串，aaa,d,bccb.所给字符串长度不会超过1000.
|
|
输入
|
|
一行，包括符合题目描述的一个字符串。
|
|
输出
|
|
一个数，表示可分成回文串的最少个数。
|
|
输入示例
|
|
aaadbccb
|
|
输出示例
|
|
3
|
#include
#include
#include
#include
#include
using namespace std;
char a[1010];
int dp[1010];
bool huiwen(int left,int right)//判断划分后是否是回文串
{
while(left<right)
{
if(a[left]!=a[right])
return 0;
left++;
right--;
}
return 1;
}
int main()
{
int l;
scanf("%s",a+1);//输入时让下标从1开始
l=strlen(a+1);
for(int i=1;i<=l;i++)
{
dp[i]=i+1;
for(int j=1;j<=i;j++)
{
if(huiwen(j,i))
dp[i]=min(dp[i],dp[j-1]+1);//dp[i]表示以i结尾的字符串最少可以分割的数量,前者为新字符归到原来的回文字符串，后者为新的字符变为新的字符串。
}
}
printf("%d",dp[l]);
return 0;
}