涂色PAINT

题意：
给你一串字符串， 用尽量少的涂色次数达到目标。
题解：
该题本质是区间dp，设字符串为s.我们定义dp[i][j]为达到s[i,j]目标最少的涂色次数.
当[i,j]长度为1时,dp[i][j]=1;
当[i,j]长度为2时,dp[i][j]=(s[i]==s[j])?1:2;
当[i,j]长度大于2时：
1.s[i]==s[j]，区间端点相同，可以看成是在比该区间小一个单位的基础上顺带涂上的
dp[i][j]=min(dp[i+1][j],dp[i][j-1]);
2.s[i]!=s[j],咱们可以把它分成两半，枚举中间点
dp[i][j]=min(dp[i][k]+dp[k+1][j],dp[i][j]);

代码：

#include <bits/stdc++.h>
using namespace std;
const int maxn=1e3+10;
int n,dp[maxn][maxn];
char s[maxn];
int main()
{
    int i,j,k,lenS,len;
    while(scanf("%s",s+1)!=EOF){
        lenS=strlen(s+1);
        for (len=1;len<=lenS;len++){
            for (i=1;i<=lenS;i++){
                j=i+len-1;
                if(j>lenS)break;
                if(len==1)dp[i][j]=1;
                else if(len==2)dp[i][j]=(s[i]==s[j])?1:2;
                else{
                    if(s[i]==s[j])dp[i][j]=min(dp[i+1][j],dp[i][j-1]);
                    else{
                        dp[i][j]=j-i+1;
                        for (k=i;k<j;k++)dp[i][j]=min(dp[i][k]+dp[k+1][j],dp[i][j]);
                    }
                }
            }
        }
        printf("%d\n",dp[1][lenS]);
    }
    return 0;
}