最少插入字符
给定字符串，可以通过插入字符，使其变为回文。求最少插入字符的数量。例如：
1. ab最少插入1个字符，变为bab
2. aa最少插入0个字符
3. abcd最少插入3个字符，dcbabcd
分析
这个题目的分析思路，和前面两期是非常相似的：给出递归的解法，发现重复的子问题，改进为动态规划的解法，这是一个分析的过程，待同学们比较熟悉时候，可以直接给出动态规划的解决方案，就很好了。
这个题目，递归该如何解呢？给定一个字符串str，长度为n，怎么插入最少的字符，是的字符串变为回文呢？插入最少的字符，就是要尽量利用原来的字符，在原字符串str中，尽量利用更多能够匹配的字符。怎么对这个问题进行分解呢？考虑str字符串整体：
1. 如果str[0]==str[n-1]，则问题转变为求str[1,n-2]，插入最少字符，得到回文
2. 如果str[0]!=str[n-1]，则需要插入一个字符要么和str[0]相同，要么和str[n-1]相同，
3. 如果和str[0]，则转变为str[1,n-1]，插入最少字符，得到回文
4. 如果和str[n-1]，则转变为str[0,n-2]，插入最少字符，得到回文
上面的第2种情况中，需要取两个值最小值。则完成了问题的分解，并且，基本情况也分析完全，则有递归式为：
fmi(str, l, h) = (str[l] == str[h]) ? fmi(str, l+1, h-1) : (min(fmi(str, i+1, h), fmi(str,l, h-1))+1)
通过上面的式子，有经验的、熟练的同学，很直接的就能看出来，存在重复的子问题，这就意味着，我们可以讲子问题的解缓存使用。如果，没有直接能够看出来的同学们，还是可以按照我们之前的方法，把递归树画出来吧，那样更加一目了然。
那么，这个题目该如何用动态规划的解决呢？如何重复利用子问题的解呢？似乎有些不那么直接。但其实也是于规律可循的。上面的递归式，是从字符串的两 边，想中间移动递归，根据动态规划解决问题的思想，我们先解决子问题，再重复利用子问题，就是要从内向外解决，大家还记得回文子串判断的那个题目么，动态 规划解法的外层循环是子串的长度，这个题目也是类似的。示例代码如下：
1 public class Solution {
2 public int constructPalindrome(String s) {
3 int length = s.length();
4 int[][] map = new int[length][length];
5 for (int offset = 1; offset < length; offset++) {
6 for (int i = 0, j = offset; i < length - offset; i++, j++) {
7 if (i == j - 1) {
8 if (s.charAt(i) != s.charAt(j)) {
9 map[i][j] = 1;
10 }
11 } else {
12 if (s.charAt(i) != s.charAt(j)) {
13 map[i][j] = Math.min(map[i][j - 1], map[i + 1][j]) + 1;
14 } else {
15 map[i][j] = map[i + 1][j - 1];
16 }
17 }
18 }
19 }
20 return map[0][length - 1];
21 }
22 }