codeforces 607B Zuma 区间dp

https://vjudge.net/problem/CodeForces-607B
题目大意：给出数组$a$a，每次操作可以从$a$a中选取一段回文串删去，问最少需要几次操作可以删去所有的元素。

思路：区间$dp$dp，$dp[i][j]$dp[i][j]表示删去区间$[i,j]$[i,j]最少需要的操作次数，那么有转移方程：$dp[i][j]=min(dp[i[[j],dp[i][k]+dp[k+1][j]),i<=k<j$dp[i][j]=min(dp[i[[j],dp[i][k]+dp[k+1][j]),i<=k<j。注意$a[i]=a[j]$a[i]=a[j]时对$dp[i][j]$dp[i][j]的初始化即可。

#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;

int n;
int a[505];
int dp[505][505];

int main()
{
    scanf("%d",&n);
    memset(dp,INF,sizeof(dp));
    for(int i=1;i<=n;i++)
        scanf("%d",&a[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(a[i]==a[j])
            {
                if(len==2)
                    dp[i][j]=1;
                else
                    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]);
        }
    }
    printf("%d\n",dp[1][n]);
    return 0;
}