题解 | #[CQOI2007]涂色PAINT#

考虑区间,设表示将区间染色需要的最少染色次数, 然后我们考虑如何将区间合并,由于我们对于一段连续的区间可以在一次内涂完, 这就意味着如果我们就可以直接从和位置的答案里转移过来。 否者，我们就要枚举断点,将区间分为两部分染色，并将两部分的结果相加，取最小的。 具体转移方程如下:

#include <stdio.h>

int main()
{
    char s[51];
    int dp[51][51]={[0 ... 50]={[0 ... 50]=100}};
    gets(s);
    int len = strlen(s);
    for(int length=1;length<=len;++length)
    {
        for(int l=0;l<len;++l)
        {
            int r = l+length-1;
            if(r > len)
                break;
            if(l == r)
            {
                dp[l][r]=1;
                continue;
            }
            if(s[l] == s[r])
                dp[l][r] = dp[l+1][r] < dp[l][r-1] ? dp[l+1][r] : dp[l][r-1];
            else
                for(int k=l;k<r;++k)
                    dp[l][r] = (dp[l][k]+dp[k+1][r]) < dp[l][r] ? (dp[l][k]+dp[k+1][r]) : dp[l][r];
        }
    }
    printf("%d",dp[0][len-1]);

    return 0;
}