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.
