HDU 1513 - Palindrome

Problem : Given a string. Add the minimum character into it to make the new string pallindrome.
Solution : Denote f[i][j] the minimum number of character added to make s[i..j] pallindrome. Then f[i][j]=min(f[i][j-1]+1, f[i+1][j]+1, f[i+1][j-1](if s[i]==s[j])). Since there is no enough space (O(n^2)), the scroll array should be used. Thus the space is O(n), time is O(n^2).