[CQOI2007]涂色PAINT （区间dp）

题目大意：给出目标字符串，然后从空串开始涂色，每次可以任意选择一个区间涂，问最少次数。

解题思路：

区间dp问题，开一个二维dp数组，dp[i][j] 代表区间从 i 到 j 最小染色次数，可分为两种情况。

1. 如果区间两端颜色相同 s[i]==s[j] 的话，dp[i][j]=min(dp[i][j-1],dp[i+1][j]),两端只需要染一次即可，然后找染左右区间的最优解。
2. 颜色不同 s[i] !=s [j]的话 ，枚举中间分割点k，把此区间分为两部分，转换为子问题求解即可。

记得提前处理一下区间长度为1的dp值。

Code:

#include <iostream>
#include <cstdio>
#include <cmath>
#include <queue>
#include <cstring>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#define inf 0x3f3f3f3f
using namespace std;
typedef long long int ll;
const int maxn=1e2+7;

int dp[maxn][maxn];
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    string s;
    cin>>s;
    int len=s.length();
    s=' '+s;
    memset(dp,inf,sizeof dp);
    for(int i=1;i<=len;i++) dp[i][i]=1;

    for(int z=2;z<=len;z++){             //区间长度
        for(int i=1;i+z-1<=len;i++){      //区间左端点
            int j=i+z-1;                //区间右端点
            if(s[i]==s[j]) dp[i][j]=min(dp[i+1][j],dp[i][j-1]);
            else{
                for(int k=i;k<j;k++){
                    dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]);
                }
            }
        }
    }
    cout<<dp[1][len]<<endl;
    return 0;
}