Pairs of Four

#include<stdio.h>
#include<algorithm>
using namespace std;
int n;
char arr[1010];

int dp[1010][1010];

int cal(int L,int R)
{
    if(L>=R)return 0;
    if(dp[L][R] != -1)return dp[L][R];
    int maxa = cal(L+1,R);
    for(int m = L + 1 ; m <= R ; m ++){
        if(arr[L] == arr[m])
            maxa = max(maxa , cal(L+1,m-1) + cal(m+1,R) + 1);
    }
    return dp[L][R] = maxa;
}

int main()
{
    for(int i = 0 ; i < 1010 ; i ++)for(int j = 0 ; j < 1010 ; j ++)dp[i][j] = -1;
 //   freopen("input3.txt","r",stdin);
    scanf("%d",&n);
    for(int i = 0 ; i < n ; i ++){
        scanf(" %c",&arr[i]);
    }
    printf("%d",cal(0,n-1));
    return 0;
}