[DP] 来一道关于palindrome的新题/变形

You are given an input string S. You are required to form a palindrome by adding 0 or more characters to the string at any location which you find appropriate. Return the minimum number of characters which needs to be added to the string to transform it into a palindrome.

For example:

(1) abab => 1 (we can append an 'a' to the string to form a palindrome.)

(2) abacaba => 0 (it's already a palindrome)

(3) abca => 1 (add a 'b' after 'c')