这道题对于区间进行涂色，就往区间dp上想。
区间dp肯定是从小区间合并到大区间，所以状态就写出来了。即dp[ i ][ j ]代表从 i 到 j 的区间中的最小方案数。
同时，在每一次取 i 和 j 的时候，我们在 i 到 j 中枚举 k ，借此来枚举所有的区间分割情况。
所以dp方程即为dp[ i ][ j ] = min ( dp[ i ][ j ] , dp[ i ][ k ] + dp[ k + 1][ j ]);
同时我们要考虑尽量的删减涂色的次数。而当一段区间两端颜色相同时，我们不需要分别涂两端，而是先涂一笔，再在两端区间内涂色即可。所以如果当第 i 个颜色和第 j 个颜色相同时，我们将dp[ i ][ j ] - -;
代码如下：
1 #include<cstdio>
2 #include<cmath>
3 #include<algorithm>
4 #include<cstring>
5 using namespace std;
6 int n,dp[1005][1005];
7 char c[1005];
8 int main()
9 {
10 scanf("%s",c);
11 n = strlen(c);
12 for(int i=0; i<n; i++)
13 for(int j=0; j<n; j++)
14 dp[i][j] = 100000005;
15 for(int i=0; i<n; i++) dp[i][i] = 1;
16 for(int i=1; i<n; i++)
17 {
18 for(int j=0; j<n; j++)
19 {
20 for(int k=j; k<i+j; k++)
21 {
22 dp[j][i+j] = min(dp[j][k]+dp[k+1][i+j],dp[j][j+i]);
23 }
24 if(c[j] == c[i+j]) dp[j][i+j]--;
25 // printf("%d %d %d
",j,i+j,dp[j][j+i]);
26 }
27 }
28 printf("%d",dp[0][n-1]);
29 return 0;
30 }