Here is my idea for O(N²) dynamic programming solution (got AC):

Let our state be:

F[L][R] = the minimum amount of characters to insert to make the substring S_LS_L + 1...S_R a palindrome.

Obviously the answer would be F[1][n]. Now let's come up with a recursive formula:

Suppose that we are trying to find the answer for some F[L][R]. We can see that at least one of the following three cases will always be true for any solution:

1) We add a character to the end to match S_L — in that case, after that one move, we end up trying to make S_L + 1...S_R a palindrome. So the outcome of this case is F[L + 1][R] + 1.

2) We add a character to the beginning to match S_R — in that case, after that one move, we end up trying to make S_L...S_R - 1 a palindrome. So the outcome of this case is F[L][R - 1] + 1

3) We match S_L with S_R. This is only possible if they are equal and in that case we have the outcome of F[L + 1][R - 1]

This gives us a simple formula:

F[L][R] = MIN(F[L + 1][R] + 1,  F[L][R - 1] + 1) for S_L ≠ S_R

F[L][R] = MIN(F[L + 1][R] + 1,  F[L][R - 1] + 1,  F[L + 1][R - 1]) for S_L = S_R

Base cases are for R ≤ L, F[L][R] = 0

The complexity is O(N²) for both time and memory. Hope that helps :)