最少插入字符
給定字符串，可以通過插入字符，使其變?yōu)榛匚摹Ｇ笞钌俨迦胱址臄?shù)量。例如：
1. ab最少插入1個字符，變?yōu)閎ab
2. aa最少插入0個字符
3. abcd最少插入3個字符，dcbabcd
分析
這個題目的分析思路，和前面兩期是非常相似的：給出遞歸的解法，發(fā)現(xiàn)重復(fù)的子問題，改進(jìn)為動態(tài)規(guī)劃的解法，這是一個分析的過程，待同學(xué)們比較熟悉時候，可以直接給出動態(tài)規(guī)劃的解決方案，就很好了。
這個題目，遞歸該如何解呢？給定一個字符串str，長度為n，怎么插入最少的字符，是的字符串變?yōu)榛匚哪兀坎迦胱钌俚淖址褪且M量利用原來的字符，在原字符串str中，盡量利用更多能夠匹配的字符。怎么對這個問題進(jìn)行分解呢？考慮str字符串整體：
1. 如果str[0]==str[n-1]，則問題轉(zhuǎn)變?yōu)榍髎tr[1,n-2]，插入最少字符，得到回文
2. 如果str[0]!=str[n-1]，則需要插入一個字符要么和str[0]相同，要么和str[n-1]相同，
3. 如果和str[0]，則轉(zhuǎn)變?yōu)閟tr[1,n-1]，插入最少字符，得到回文
4. 如果和str[n-1]，則轉(zhuǎn)變?yōu)閟tr[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)
通過上面的式子，有經(jīng)驗的、熟練的同學(xué)，很直接的就能看出來，存在重復(fù)的子問題，這就意味著，我們可以講子問題的解緩存使用。如果，沒有直接能夠看出來的同學(xué)們，還是可以按照我們之前的方法，把遞歸樹畫出來吧，那樣更加一目了然。
那么，這個題目該如何用動態(tài)規(guī)劃的解決呢？如何重復(fù)利用子問題的解呢？似乎有些不那么直接。但其實也是于規(guī)律可循的。上面的遞歸式，是從字符串的兩 邊，想中間移動遞歸，根據(jù)動態(tài)規(guī)劃解決問題的思想，我們先解決子問題，再重復(fù)利用子問題，就是要從內(nèi)向外解決，大家還記得回文子串判斷的那個題目么，動態(tài) 規(guī)劃解法的外層循環(huán)是子串的長度，這個題目也是類似的。示例代碼如下：
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 }