背景
今天和舍友聊到算法题，他问了这道题，觉得挺有意思，故写下解题思路。老久没做算法题了，偶尔搞搞还是挺有意思。
题目描述
给定一个字符串S，可以通过在字符串的任意位置插入字符，使其变为回文串。求最少插入字符的数量。
例如：
ab -> bab 1
aa -> aa 0
abca -> acbca 1
题目来源：微信号 待字闺中
解题思路
如果能在原串S中找到最长的子序列L，这个子序列是回文，那么我们就能知道要插入多少个字符是的原串成为回文。
ans = strlen(s) - strlen(L)
问题转为求一个字符串的最长回文子序列，这个问题可以使用最长公共子序列的解法，解法如下：
1.求S的逆序串 S',；
2.那么S和S'的用求最长公共子序列L，L即为S的最长回文子序列(这个规律是在推演中发现的)；
3.那么问题得解：ans = strlen(s) - strlen(L)。
例如： S = abca 那么 S' = acba ，那么L = aba 那么答案就是1.即 a’c‘bca。其中'c'为插入的字符。
算法分析
该算法的核心是求最长公共子序列，最长公共子序列有DP的求法，算法的复杂度是 时间和空间都是 O(n^2)
解法二
原作者提供
主要采用动态规划，动态规划主要从两端字符进行比较，因而有重复子问题。
假设将问题表示为公式S(0,n-1)，那么
if(a[0] = a[n-1])
s(0,n-1) == s(2,n-2)
else
s(0,n-1) == min( s(1,n-2) , s(2,n-1) ) + 1
s(0,n-1) == s(2,n-2)
else
s(0,n-1) == min( s(1,n-2) , s(2,n-1) ) + 1
其中a[i]为串S中的第i个字符。