解题步骤：

step 1: 设立状态。按照惯例，设f[i][j]表示从i到j的区间修改为目标状态的所需步数

step 2: 初始化。长度为1的区间可以直接算出，从没有涂色到给定的颜色需要涂一次色。

step 3: 枚举起点、终点，推出答案。 当第i个字符与第j个字符相同时，只需在第一次涂色时多涂一个即可。所以f[i][j]=min(f[i+1][j],f[i][j-1]) (缩小区间) 不同时，枚举断点k(i<=k<j)，则f[i][j]=断点左边修改次数+断点右边修改次数，即f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]);

step 4: 输出。结果=f[1][n];

附上dp代码：

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cstdlib>
using namespace std;
const int N=55;
int f[N][N];
char a[N];
// 区间DP：f[i][j]表示把从i到j的字符串修改为目标状态需要多少次
int main(){
    scanf("%s",a+1);
    int n=strlen(a+1);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(i==j)
                f[i][j]=1;
            else
                f[i][j]=1<<30; //因为答案要求最小，所以初始化要大
        }
    }
    for(int l=2;l<=n;l++){//模板
        for(int i=1;i<=n;i++){
            int j=i+l-1;
            if(j>n)
                break;
            if(a[i]==a[j])//相同时
                f[i][j]=min(f[i+1][j],f[i][j-1]);
            for(int k=i;k<j;k++)//不同时
                f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]);
        }
    }
    printf("%d\n",f[1][n]);
    //system("pause");
    return 0;
}

还有记忆化搜索代码: (事实说明dfs更好点：dp-47ms/1800多kb, dfs-28ms/820kb)

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cstdlib>
using namespace std;
const int N=55;
int f[N][N],n;
char a[N];
int dfs(int l,int r){ //模板
    if(l==r)
        return f[l][r]=1;//递归到底层，相当于dp中的初始化条件
    if(f[l][r]!=-1)
        return f[l][r];//已经计算过了，调用
    int tmp=1<<30;
    if(a[l]==a[r])
        tmp=min(dfs(l+1,r),dfs(l,r-1));//解释同dp代码
    for(int k=l;k<r;k++)
        tmp=min(tmp,dfs(l,k)+dfs(k+1,r));
    return f[l][r]=tmp;
}
int main(){
    scanf("%s",a+1);
    n=strlen(a+1);
    memset(f,-1,sizeof(f));//标记为没有计算过
    printf("%d\n",dfs(1,n));
    return 0;
}