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.
https://gist.github.com/fredbr/55185bcfaf14ed7551053ea569ef3f02