Solução Informática Avançado - Semana 58

Solução por Leonardo Paes

Para resolver este problema, utilizaremos programação dinâmica.

Seja $DP_{l, r}$ a resposta para a substring $S_{l, l + 1, \dots, r}$ .

Então, temos dois casos para considerar:

A primeira letra da substring é deletada separadamente do resto, então $DP_{l, r} = 1 + DP_{l+1, r}$ .
A primeira letra da substring é deletada juntamente com alguma outra letra (ambas as letras devem ser iguais), então: $DP_{l, r} = \min \limits_{l < i \le r, S_i = S_r} DP_{l + 1, i - 1} + DP_{i, r}$ .

Segue abaixo o código para melhor entendimento:

	#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.
	}