題目
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
分析（錯誤）
將word1轉(zhuǎn)換成word2，無法缺少的步驟是刪除或者插入解孙，從而使得兩者的長度一致坑填。在此前提下，如何盡可能利用word2中原有的字符才是關(guān)鍵弛姜。所以本題可以轉(zhuǎn)換為：尋找在word2中與word1中相同且依次出現(xiàn)的多字符個數(shù)（可以不連續(xù)也可以跳過）脐瑰。
后來按照這個思路完成的一次實現(xiàn)中，發(fā)現(xiàn)了反例……例如word1為"ab"廷臼，word2為"bc"則該思路不成立苍在。
分析二
直接考慮兩個字符串之間的最小轉(zhuǎn)化距離。若已知字符串A和字符串B的最小轉(zhuǎn)化距離為dp[i-1][j-1]荠商，則考慮添加一個字母之后的字符串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
取三者最小值即可牙咏，得到此時狀態(tài)轉(zhuǎn)移方程為
dp[i][j]=min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1])+1
實現(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];
}
};
思考
動態(tài)規(guī)劃真的是嘹裂，沒想出來的時候覺得難死丁寄。想出來了覺得豁然開朗宁舰。雖然過程很痛苦，但是完成之后所獲得的成就感也是巨大的。
