题目大意:输入一个由小写字母组成的字符串,你的任务是把它划分成尽量少的回文串。比如racecar本身就是回文串;fastcar只能分成7个单字母的回文串;aaadbccb最少可分成3个回文串:aaa、d、bccb。字符串的长度不超过1000。
分析:令dp[i]表示从第1个到第 i 个字符所组成的最少回文串数。
我们考虑如果前k个字符构成了1个回文,那么前k+1个字符最多构成2个回文,如果这些字符都相同,那么也只是1个回文串。所以如果第 j 个字母到第 i 个字母能构成回文,那么dp[i] = min(dp[i],dp[j-1]+1);
初始条件是:dp[i]=i;
代码如下:
# include<cstdio>
# include<cstring>
# include<iostream>
using namespace std;
char s[];
int dp[];
bool judge(int i,int j){
for(int k=;k<=(j-i)/;k++)
if(s[i+k] != s[j-k])
return false;
return true;
}
int main(){
int T,i,j,len;
scanf("%d",&T);
while(T--){
scanf("%s",s);
dp[] = ;
len =strlen(s);
for(i=; i<=strlen(s);i++){
dp[i] = i;
for(j=;j<=i;j++){
if(judge(j-,i-))
dp[i] = min(dp[i],dp[j-]+);
}
}
printf("%d\n",dp[len]);
}
return ;
}