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