思路是找到每个颜色不相同的区间，然后转移。
结果偏大，这是另一个版本：
```cpp
#include <bits/stdc++.h>
using namespace std;
int n,f[600][600];
char a[600];
int main()
{
scanf("%s",a);
n=strlen(a);
for(int i=0;i<n;i++)f[i][i]=1;
for(int l=2;l<=n;l++)
for(int i=0;i+l-1<n;i++)
{
int j=i+l-1;
f[i][j]=99999999;
for(int m=i;m<=j;m++)
{
int ans=0;
int z=-1,y=-1;
for(int k=i;k<=j;k++)
{
if(a[k]==a[m]&&z!=-1)y=k-1,ans+=f[z][y],z=-1;
if(a[k]!=a[m]&&z==-1)z=k;
}
if(z!=-1)ans+=f[z][j];
f[i][j]=min(f[i][j],ans+1);
}
for(int k=i;k<j;k++)
f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]);
}
printf("%d",f[0][n-1]);
return 0;
}
```
by w9095 @ 2022-12-24 15:18:50
P4170 [CQOI2007]涂色
您的HACK数据（手测出的）：
ABCACBA
答案4，输出5
by Huanglf0910 @ 2023-01-01 10:58:54
@[Huanglf0910](/user/699992) 已AC，谢谢dalao
by w9095 @ 2023-01-02 09:17:25