正如 @dXqwq 所说，题解做法都十分难以想到。

考虑一种复杂度相同，但是好想很多的一种区间 dp（不知道重没重？）

考虑先把操作倒过来，每次相当于把一段颜色全相同或为 * 的区间变为 *，求最少把字符串变成全 * 的步数。

考虑设 $f_{l,r}$ 表示 $s_{l\sim r}$ 的答案。找到倒过来之后的最后一步，也就是开头第一步。把还不是 * 的所有位置提出来，那么它们一定全相等，而中间的部分互相独立，因此就可以用已经求出的 dp 值来转移。

具体地，倒序枚举 $l$，这是一个经典的区间 dp 套 dp（可能不太应该这么叫），就是再增加一个 $d_x$ 表示最后一个不是 * 的字符的位置是 $x$，互相转移即可。

#include<bits/stdc++.h>
using namespace std;
char s[55];
int f[55][55];
int d[55];
int main(){
	scanf("%s",s+1);
	int n=strlen(s+1);
	memset(f,63,sizeof(f));
	for(int i=1;i<=n+1;++i)f[i][i-1]=0;
	for(int i=n;i>=1;--i){
		memset(d,63,sizeof(d));
		d[i-1]=0;
		for(int j=i;j<=n;++j){
			for(int k=i-1;k<j;++k)if(k==i-1||s[k]==s[j]){
				d[j]=min(d[j],d[k]+f[k+1][j-1]);
			}
			for(int k=i;k<=j;++k){
				f[i][j]=min(f[i][j],1+d[k]+f[k+1][j]);
			}
		}
	}
	printf("%d\n",f[1][n]);
	return 0;
}