样例都过不去，找了半小时错了。。

就是区间 dp，状态转移方程和第一篇题解差不多。

#include<cstdio>
#include<algorithm>
#include<map>
#include<cstring>

#define MAXN 100
#define LL long long

using namespace std;

int dp[MAXN][MAXN];
char ch[MAXN];

inline int read(){
	int out=0,flag=1;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')flag=-1;c=getchar();}
	while(c>='0'&&c<='9'){out=out*10+c-'0';c=getchar();}
	return flag*out;
}

const int INF=0x7fffffff;

int main(void){
	
	scanf("%s",ch+1);
	int len=strlen(ch+1);
	for(int i=1;i<=MAXN;i++){
		for(int j=1;j<=MAXN;j++){
			dp[i][j]=INF;
		}
	}
	for(int i=1;i<=len;i++)dp[i][i]=1;
	for(int l=2;l<=len;l++){
		for(int i=1,j=l;j<=len;i++,j++){
			if(ch[i]==ch[j])dp[i][j]=min(dp[i+1][j],dp[i][j-1]);
			else{
				for(int k=i;k<j;k++){
					dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]);
				}
			}
		}
	}
	
	printf("%d\n",dp[1][len]);
	
	return 0;
}