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.