vva11584dp 최소 회신 문자열 구분

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
char str[1010];
int flag[1010][1010];
int dp[1010];
int l;
const int INF=0x3f3f3f3f;
void pre()
{
	/* flag[i][j]=1     i str  j          ，
	  flag[i][j]=0*/
	memset(flag,0,sizeof(flag));
	for(int i=1;i<=l;i++)flag[1][i]=1;
	if(l==1)return;
	for(int i=1;i<=l-1;i++)if(str[i]==str[i+1])flag[2][i]=1;
	for(int i=3;i<=l;i++)
	for(int j=1;j<=l-i+1;j++)
	{
		/*j  i           j+1  i-2   
			                  */
		if(flag[i-2][j+1] && str[j]==str[j+i-1])
		flag[i][j]=1;
	}
}
void solve()
{
	for(int i=1;i<=l;i++)dp[i]=INF;
	dp[0]=0;
	for(int i=1;i<=l;i++)
	for(int j=1;j<=i;j++)
	{
		// i  ，   j     
		//f[i]    i  ，        ，
		//     i     j       
		if(flag[j][i-j+1])
		{
			//f[i]=min{f[i-j]+1}(if flag[j][i-j+1]=1}
			dp[i]=min(dp[i],dp[i-j]+1);
		}
	}
}
int main()
{
	int T;
	scanf("%d",&T);
	while(T--)
	{
        scanf("%s",str+1);
		l=strlen(str+1); 
		pre();
		solve();
		printf("%d
",dp[l]);
	}
	return 0;
} 

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int INF=0x3f3f3f3f;
char str[1010];
int dp[1010];
int len;
bool check(int l,int r)
{
	for(int i=l,j=r;i<=r;i++,j--)
	if(str[i]!=str[j])return false;
	return true;	
}
int main()
{
	int T;
	scanf("%d",&T);
	while(T--)
	{
		scanf("%s",str+1);
		len=strlen(str+1);
		for(int i=1;i<=len;i++)dp[i]=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[j-1]+1}
				dp[i]=min(dp[i],dp[j-1]+1);
			}
		}
		printf("%d
",dp[len]);
	}
	return 0;
}