[CQOI2007]涂色PAINT

题意：
给你目标字符串的状态，现可以将连续一段字符串染色，求最小的染色次数
题解：
我们定义dp[i][j]是区间i到区间j最小的涂色次数
区间dp的核心思想实际上是由一个个小区间进行合并成为大区间，所以我们在dp的时候应该从长度最短的下手，也就是长度为1的。
1.长度为1的区间，涂色次数为1.
2.长度区间为2的值：
它可以由两个长度为1的区间和并，但是这个题目比较特殊的一点就是，你图一次可以连续涂一个区间，所以如果s[i]==s[j]那么这个区间只需要涂一次，如果不同，那么就是两个区间次数的相加了。
3.长度为n的值：
仿照区间长度为2的时候，我们可以枚举区间中的某个分割点来进行递推，这就跟Floyd的核心思想差不多了（Floyd其实本质就是动态规划）。
但是这个题的要求，涂一次可以涂一个连续的区间，所以说，如果s[i]==s[j]，那么我们就可以直接转移左区间或者右区间，因为涂一次可以图一个连续的区间。
综上所述：
转移方程
1. i==j时：dp[i][j]=1;
2. 当i!=j且s[i]==s[j]时：dp[i][j]=min(dp[i][j-1],dp[i+1][j])
3. 当i!=j且s[i]!=s[j]时：我们就需要枚举断电k ，dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j])

代码：

/*Keep on going Never give up*/
#pragma GCC optimize(3,"Ofast","inline")
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <stdlib.h>
#include <queue>
#include <string>
const int maxn = 100;
const int MaxN = 0x3f3f3f3f;
const int MinN = 0xc0c0c00c;
typedef long long ll;
const ll mod = 1e9+7;
using namespace std;
int dp[maxn][maxn];
char s[maxn];
int main(){
    scanf("%s",s+1);
    memset(dp,MaxN,sizeof dp);
    for(int i=0;i<=strlen(s+1);i++) dp[i][i]=1;
    for(int len=1;len<=strlen(s+1);len++){
        for(int i=1,j=i+len;j<=strlen(s+1);i++,j++){
            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][strlen(s+1)]<<endl;
    return 0;
}