題目

Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 step.)

You have the following 3 operations permitted on a word:

a) Insert a character
b) Delete a character
c) Replace a character

分析（錯(cuò)誤）

將word1轉(zhuǎn)換成word2，無(wú)法缺少的步驟是刪除或者插入，從而使得兩者的長(zhǎng)度一致。在此前提下，如何盡可能利用word2中原有的字符才是關(guān)鍵。所以本題可以轉(zhuǎn)換為：尋找在word2中與word1中相同且依次出現(xiàn)的多字符個(gè)數(shù)（可以不連續(xù)也可以跳過(guò)）。
后來(lái)按照這個(gè)思路完成的一次實(shí)現(xiàn)中，發(fā)現(xiàn)了反例……例如word1為"ab"，word2為"bc"則該思路不成立。

分析二

直接考慮兩個(gè)字符串之間的最小轉(zhuǎn)化距離。若已知字符串A和字符串B的最小轉(zhuǎn)化距離為dp[i-1][j-1]，則考慮添加一個(gè)字母之后的字符串Ax和By的最小轉(zhuǎn)化距離dp[i][j]。

• 若x==y，則有dp[i][j]=dp[i-1][j-1]
• 若x!=y，則有三種情況
  1)將x替換為y，則有dp[i][j]=dp[i-1][j-1]+1
  2)刪去x，則有dp[i][j]=dp[i-1][j]+1
  3)添加y，則有dp[i][j]=dp[i][j-1]+1
  取三者最小值即可，得到此時(shí)狀態(tài)轉(zhuǎn)移方程為
  dp[i][j]=min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1])+1

實(shí)現(xiàn)

class Solution {
public:
    int minDistance(string word1, string word2) {
        int m=word1.size(), n=word2.size(), dp[m+1][n+1];
        for(int i=0; i<=m; i++)
            dp[i][0] = i;
        for(int j=0; j<=n; j++)
            dp[0][j] = j;
        for(int j=1; j<=n; j++){
            for(int i=1; i<=m; i++){
                if(word1[i-1]==word2[j-1])
                    dp[i][j] = dp[i-1][j-1];
                else
                    dp[i][j] = min(dp[i-1][j-1], min(dp[i-1][j], dp[i][j-1])) + 1;
            }
        }
        return dp[m][n];
    }
};

思考

動(dòng)態(tài)規(guī)劃真的是，沒(méi)想出來(lái)的時(shí)候覺(jué)得難死。想出來(lái)了覺(jué)得豁然開(kāi)朗。雖然過(guò)程很痛苦，但是完成之后所獲得的成就感也是巨大的。