链接: https://vjudge.net/problem/UVA-11584
分析:设dp[i]为1-i个字符划分成的最小回文串的个数,
状态转移方程:dp[i]=min(dp[i],dp[j-1]+1), 第j到第i个字符为回文串
dp[0]=0; 其余初始化为INF
每次输入从字符串数组的第二个位置str[1]开始输入,从第一个位置输入得不到正确答案!
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define mem(a,n) memset(a,n,sizeof(a))
const int INF=0x3f3f3f3f;
const int N=1e3+5;
int dp[N];
char str[N];
bool check(int j,int i)
{
while(j<=i)
{
if(str[j]!=str[i])
return false;
else j++,i--;
}
return true;
}
int main()
{
int n;
while(~scanf("%d",&n))
{
while(n--)
{
scanf("%s",str+1);
int len=strlen(str+1);
mem(dp,INF);
dp[0]=0;
for(int i=1; i<=len; i++)
for(int j=1; j<=i; j++)
{
if(check(j,i))
dp[i]=min(dp[i],dp[j-1]+1);
}
printf("%d\n",dp[len]);
}
}
return 0;
}