Dynamic Programming problem palindrome

Question

I am stuck with the following problem:

Given a string of characters $w$, we want to know the minimum number of characters that we must add to $w$ in order to convert this string in a palindrome (note that we can add characters in any position of the string $w$)

This problem was given in one of my algorithms classes and the key was to solve it by dynamic programming. The suggestion given for this problem was to think of a function that takes two parameters $i,j$ to transform the string $a_i...a_j$.

I'll give a few examples of the problem at hand to illustrate:

• $b$ is converted to the palindrome string $b$ by adding $0$ characters
• $ab$ is converted to $aba$ by adding $1$ character
• $adaf$ is converted to $fadaf$ by adding $1$ character
• $abc$ is converted to $abcba$ by adding $2$ characters

I couldn't come up with any ideas to define a function $f(i,j)$ that helps to construct a dynamic programming solution, any suggestions with a dynamic programming approach towards the solution would be really appreciated.

Answer 1

This is a well known problem with a dozen of variants all over the web. This page offers several solutions, including a dynamic one:

Minimum insertions to for a palindrome