【区间dp】Codeforces Round 336 (Div 2) D Zuma

Codeforces Round 336 (Div 2) D Zuma

题意：给一个长度为n的字符串，每次可以删掉其中的一个回文子串，问你最少需要删多少次

思路：拿到的时候我愣了一下，没想到是区间dp，emm，事实上它和经典区间dp括号匹配是一样的思路

dp[i][j]代表i~j删完需要的次数，if(c[i]==c[j]) dp[i][j]=dp[i+1][j-1] （可以和i+1~j-1连成回文串）

注意特判长度为2，不能转移到dp[i+1][j-1]，而是为1

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=510;
const int INF=0x3f3f3f3f;
int c[N];
int n;
int dp[N][N];
int main()
{cin>>n;for(int i=1;i<=n;++i)cin>>c[i];memset(dp,INF,sizeof(dp));for(int i=1;i<=n;++i)dp[i][i]=1;for(int len=2;len<=n;++len){for(int i=1;i+len-1<=n;++i){int j=i+len-1;if(c[i]==c[j]){if(len==2) dp[i][j]=1;            //注意！test 3else dp[i][j]=dp[i+1][j-1];}for(int k=i;k<j;++k)dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]);}}cout<<dp[1][n]<<endl;return 0;}