TOI10: Pair of Fours

#include <bits/stdc++.h>

using namespace std;

char ar[1010];
int n;
int dp[1010][1010];

int recur(int i, int j){
    if(i == j or j < i) return dp[i][j] = 0;
    if(dp[i][j] != 0) return dp[i][j];
    if(ar[i] == ar[j]) return dp[i][j] = 1 + recur(i+1, j-1);
    if(i + 1 == j) return 0;
    for(int k=i;k<j;k++){
        dp[i][j] = max(dp[i][j], recur(i, k) + recur(k+1, j));
    }
    return dp[i][j];
}

int main(){

    scanf("%d", &n);

    for(int i=1;i<=n;i++) scanf(" %c", &ar[i]);

    for(int i=n;i>=1;i--){
        for(int j=i+1;j<=n;j++){
            if(i == j or j < i) dp[i][j] = 0;
            if(ar[i] == ar[j]) dp[i][j] = 1 + dp[i+1][j-1];
            if(i + 1 == j) dp[i][j] = 0;
            else{
                for(int k=i;k<j;k++){
                    dp[i][j] = max(dp[i][j], dp[i][k] + dp[k+1][j]);
                }
            }
        }
    }

    printf("%d", dp[1][n]);
    //printf("%d", recur(1, n));

    return 0;
}