[CQOI2007]涂色PAINT

题意：
让你对n个长度的木板染色，每次可以对连续的任意长度染同一种颜色，初始没有颜色，求最少需要染多少次能染成目标颜色？

思路：
区间dp
dp[i][j]表示从i到j的区间染成目标颜色的最少染色次数。
当第i个格子和第j个格子的颜色相同时，第i个格子可以被dp[i+1][j]顺便染成、第j个格子可以被dp[i][j-1]顺便染成。
他还可以由dp[i][o]+dp[o+1] [j] (i<=o<=j-1)转化来（二个区间的合并成一个区间，相当于一个区间分成二个区间分别染色）

代码：

#include <bits/stdc++.h>

typedef long long ll;

using namespace std;

const int inf=1000000007;

string s;
int dp[1005][1005];

int main()
{
    cin >> s;
    fill(dp[0],dp[0]+1005*1005,inf);
    int l=0, r=s.length()-1;
    for(int i=l;i<=r;i++)
    {
        dp[i][i]=1;
    }
    for(int k=2;k<=r+1;k++)
    {
        for(int i=0;i+k-1<=r;i++)
        {
            int j=i+k-1;
            if(s[j]==s[i])
            {
                dp[i][j]=min(dp[i+1][j],dp[i][j-1]);
            }
            for(int o=i;o<=j;o++)
            {
                dp[i][j]=min(dp[i][j],dp[i][o]+dp[o+1][j]);
            }
        }
    }
    cout << dp[0][r] << endl;
    return 0;
}