/******************************************************************************
?????????????????????????動態規劃--最短編輯問題????????????????????????????????????????????????????????
*******************************************************************************/?


/*?
*問題描述：設A?和B?是2?個字符串。要用最少的字符操作將字符串A?轉換為字符串B。
*??????????這里所說的字符操作包括?（1）刪除一個字符；?（2）插入一個字符；?
*??????????（3）將一個字符改為另一個字符。將字符串A變換為字符串B?所用的最少
*??????????字符操作數稱為字符串A到B?的編輯距離，記為?d（AB）。試設計一個有效
*??????????算法，對任給的2?個字符串A和B，計算出它們的編輯距離d（AB）。
*??????????例如：
*??????????輸入第一個字符串：?
*??????????shao
*??????????輸入第二個字符串：?
*??????????shaod?
*??????????最短編輯距離
*??????????1?
*
*分析：????（1）選擇動態規劃的理由：
*??????????由于該問題是計算最短編輯問題的，要求兩個字符串的最短編輯距離時，當?????
*??????????該字符串的子串滿足最短編輯距離的時候，那么該字符串也就會滿足，但是
*??????????如何得到子串的最短編輯距離呢？我們可以考慮用回溯法來求，可是回溯法的?
*??????????缺點是會求出所有可能的路線，當求子串d[i][j]子串的時須求出d[i-1][j-1]?
*??????????然而該子串d[i-1][j-1]?已經在求d[i-1]?[j]的時候求過，用遞推的思想還有
*??????????記憶化的搜索的情況下，我就考慮到了用動態規劃。?并且由于該結構具有
*??????????重疊子問題。再加上所具有的最優子結構。符合動態規劃算法基本要素。因此
*??????????可以使用動態規劃算法把復雜度降低到多項式級別。
*?
*??????????
*??????????（2）本題思路分析
*??????????定義兩個字符串s1?s2?
*??????????比較兩字符串的某兩個相同位置時：（例如s1[i]?s2[j]?這時i=j）有三種辦法?
*??????????1.把字符ch1變成ch2，?使得s1與s2字符串在該處相同
*??????????2.刪除s1當中的該字符ch1，使得s1與s2字符串在該處相同?
*??????????3.插入某個字符ch2，使得s1與s2字符串在該處相同?
*???????????
*??????????（3）.首先為了避免重復計算子問題，添加兩個輔助數組。
*?????????????<1>?保存子問題結果。
*?????????????????d[?|s1|?|s2|?]??其中d[?i??j?]?表示子串?s1（0->i）?與?s2（0->j）
*?????????????????的編輯距離
*?????????????<2>?保存字符之間的編輯距離.
*?????????????????cost?其中?cost=?s[ch1]?=?s[ch2]???0?:?1
*??????????（4）編輯距離的性質
*??????????計算兩個字符串s1+ch1?s2+ch2的編輯距離有這樣的性質:
*??????????<1>.d（s1””）?=?d（“”s1）?=?|s1|??當某一個字符串為空時，最短編輯距離
*??????????????是另外一個字符串的長度。????
*??????????????d（“ch1””ch2”）?=?ch1?==?ch2???0?:?1;?當比較兩個字符之間的距離
*??????????????時，若兩字符相同編輯距離為0，不相同的情況編輯距離為1?
*??????????<2>.由于我們定義的三個操作來作為編輯距離的一種衡量方法。
*??????????????于是對ch1ch2可能的操作只有
*??????????????1.把ch1變成ch2???因此當ch1==ch2時，d（s1+ch1s2+ch2）??=?d（s1s2）
*???????????????????????????????????當ch1!=ch2時，d（s1+ch1s2+ch2）??=?d（s1s2）+1?
*??????????????2.s1+ch1后刪除ch1??????????????d?=?（1+d（s1s2+ch2））
*??????????????3.s1+ch1后插入ch2??????????????d?=?（1?+?d（s1+ch1s2））
*??????????????對于2和3的操作可以等價于:
*??????????????2.s2+ch2后添加ch1??????????????d=（1+d（s1s2+ch2））
*??????????????3.s2+ch2后刪除ch2??????????????d=（1+d（s1+ch1s2））
*???????????????
*
*??????????????因此：d（s1+ch1s2+ch2）?=?min（??d（s1s2）+?ch1==ch2???0?:?1?
*?????????????????????????????????????????????d（s1+ch1s2）
*?????????????????????????????????????????????d（s1s2+ch2）??）;?????
*??????????
*??????????
*??????????（5）.新的計算表達式
*??????????????
*??????????????d[?00