涂色PAINT

题意：

给定目标字符串状态，现给定一个空字符串，你每次可以对一区间进行染色，求最少染色次数。

分析：

染色问题首先想到dp，区间染色，我们定义 dp[i][j] 是区间 i 到区间 j 最小的涂色次数，那么答案就是 dp[1][n]。
区间dp求解是由小区间合并成大区间的，也就是我们要从长度最短的区间开始解决子问题，当区间长度为1时，我们不难得出其最小涂色次数为1，当区间长度大于时，最小染色次数为 左区间最小次数+右区间最小次数，因此我们需要枚举该区间每个断点所得到的最小染色次数最小值。特别的，当a[i] ==a[j] 时，可以由min（dp[i][j-1],dp[i+1][j]）进行转移过来，因为涂一次可以涂一整个区间，l或者r的那一次染色可以拿来帮助另一个染色。

综上所述：
1. 当i==j时：dp[i][j]=1;
2. 当i!=j且a[i]==a[j]时：dp[i][j]=min(dp[i][j-1],dp[i+1][j])
3. 当i!=j且a[i]!=a[j]时：我们就需要枚举断电k ，dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j])

代码：

#include<iostream>
#include<algorithm>
#include<stdio.h>
#include<cstring>
using namespace std;
#define mem(a, x) memset(a, x, sizeof(a))
typedef long long ll;
void fre() { freopen("A.txt", "r", stdin); freopen("Ans.txt","w",stdout); }
const int inf=0x3f3f3f3f;
string a;
int dp[110][110];
int main()
{
    cin>>a;
    mem(dp,0x3f3f3f);
    int n = a.size();
    a = ' ' + a;
    for(int i = 1;i <= n;i++){
        for(int j = 1;j + i - 1 <= n;j++){//枚举左端点
            int r = j + i - 1;//k为右端点
            if(r == j){
                dp[j][r] = 1;
                continue;
            }
            if(a[j] == a[r]) dp[j][r] = min(dp[j+1][r],dp[j][r-1]);
            else{
                for(int k = 1;k < r;k++){//枚举断点
                    dp[j][r] = min(dp[j][k]+dp[k+1][r],dp[j][r]);
                }
            }
        }
    }
    cout<<dp[1][n]<<endl;

}