Solução Informática Intermediário – Semana 40

Para resolver esse problema vamos procurar uma solução com programação dinâmica.

Vamos charmar a string de entrada de $$S$$, e considerar a tabela $$dp_{i,j}$$, aonde $$dp_{i,j}$$ indica a quantidade mínima de inserções para tornar o intervalo $$[i,j]$$ um palíndrome.

Para a recursão podemos considerar os seguintes casos:

• $$S_i = S_j$$ : Não necessitamos inserir nenhum caractere, nem na posição $$i$$ nem na posição $$j$$, então $$dp_{i,j} = dp_{i+1,j-1}$$
• $$S_i \neq S_j$$: Devemos inserir um caracter ou na posição $$i$$ ou na posição $$j$$, então quando inserirmos vamos procurar em qual desses lugares inserir custa menos, então $$dp_{i,j} = max(dp_{i+1,j}, dp_{i,j-1}) + 1$$
• Caso $$ i\geq j$$: Então caímos em um caso base, e então $$dp_{i,j} = 0$$

Assim podemos fazer essa recursão partindo de $$dp_{0,n-1}$$, e esse será nosso resultado.

Código para melhor entendimento:

OBS: A questão original requeria um uso de Memory Trick para economizar memória, e é por isso o código abaixo usa um vetor $$dp[2][n]$$ em vez de $$dp[n][n]$$, e também é por isso que está sendo feita de forma bottom-up.