SEMANA 57 - PROBLEMA AVANÇADO.cpp

#include <bits/stdc++.h>

using namespace std;

const int maxn = 5e2 + 100; // Número máximo de caracteres da string S.

int n, dp[maxn][maxn]; // Declaro N e a DP.

string s; // Declaro a string S.

int solve(int l, int r){
    if(dp[l][r]!=0x3f3f3f3f)return dp[l][r]; // Se já precalculamos tal substring, não a calcularemos novamente.

    if(l>r)return dp[l][r]=0; // Se l>r a substring não existe, então retornamos 0.
    if(l==r)return dp[l][r]=1; // Se l=r então basta apagarmos o seu único caractere.

    dp[l][r] = 1 + solve(l+1, r); // Caso 1.

    for(int i=l+1; i<=r; i++){
        if(s[l]==s[i])dp[l][r]=min(dp[l][r], solve(l+1, i-1) + solve(i,r)); // Caso 2.
    }
    return dp[l][r]; // Retorno a menor quantidade de operações necessárias para limpar a substring de l até r.
}

int main(){

    cin >> n; // Leio a quantidade de caracteres da string S.

    cin >> s; // Leio a string S.

    memset(dp, 0x3f3f3f3f, sizeof dp); // Digo que ainda não sei a resposta de nenhuma substring.

    cout << solve(0, n-1) << endl; // Imprimo a resposta da string S.
}