Educational Codeforces Round 61 (Rated for Div. 2) F. Clear the String//区间dp

https://codeforces.com/contest/1132/problem/F

首先，如果用一般的dp，那么维护的是【0，i】的区间，显然（...）是不能解决这题的。

然后 维护【l，r】【x】 l到r 的区间，最后删除的是x字符的最小操作次数，递推的求解（i大小和i+1大小区间似乎不能强推出来），（wawawa），https://codeforces.com/contest/1132/submission/51259380（WA代码）  

正解：

dp[l][r]删除【l，r】的最小操作次数。

对于最左边的数，选择自己单独删除，或者与右边的相同的数一起删除。

l和区间中一个进行匹配，相同时，删除【l+1，i-1】的次数+删除【i，r】的次数就是结果。

#include<bits/stdc++.h>
using namespace std;
int n;
char s[505];
int dp[505][505];
int dfs(int l,int r){
    if(dp[l][r]) return dp[l][r];
    if(l==r) return dp[l][r]=1;
    if(l>r) return 0;
    int ans=dfs(l+1,r)+1;
    for(int i=l+1;i<=r;i++){
        if(s[i]==s[l]) {
            ans=min(ans,dfs(l+1,i-1)+dfs(i,r));
        }
    }
    return dp[l][r]=ans;
}
int main(){
	ios::sync_with_stdio(false);
	cin>>n;cin>>s;
	cout<<dfs(0,n-1);
	return 0;
}

这个两个EF做的我心累。。。。。