EDU 61 F. Clear the String 区间dp

无聊做水题，

链接：http://codeforces.com/contest/1132/problem/F

题意：一个字符串一次可以消除 形如：xxxx 的子串，问最少消几次

思路：区间dp，注意左右相等的情况就好了。。。

代码：

#include<bits/stdc++.h>
#define X first
#define Y second
#define PB push_back
#define LL long long
#define VI vector<int>
#define pii pair<int,int>
#define MEM(x,y) memset(x,y,sizeof(x))
#define bug(x) cout<<"debug "#x" is "<<x<<endl;
#define FIO ios::sync_with_stdio(false);
using namespace std;
const int maxn=1e3+7;
const int mod=1e9+7;
int dp[maxn][maxn];
string s;
int DP(int L,int R){
    if(dp[L][R]!=-1)return dp[L][R];
    if(L==R) return dp[L][R]=1;
    if(s[L]==s[R]) return DP(L+1,R);
    int ret=mod;
    for(int k=L;k<R;k++)
        ret=min(ret,DP(L,k)+DP(k+1,R));
    return dp[L][R]=ret;
}

int main(){
	ios::sync_with_stdio(false);
    int n;
    MEM(dp,-1);
    string tmp;
    cin>>n>>tmp;
    s+=tmp[0];
    for(int i=1;i<tmp.size();i++)
        if(tmp[i]!=s[s.size()-1])s+=tmp[i];
    cout<<DP(0,s.size()-1)<<endl;
}