dp注意问题
递推式
初值
空间优化
1. bfs
题目里有“最小”字样，符合bfs关键词：上界len(S)+len(T)
实际上不可行；
2. dp
删除字符很麻烦
换个角度，变为字符串“对齐问题”：
S = ABCF
T = DBFG
S：A B C F -
T：D B - F G
对应位置相同则不扣分，不同则扣一分（需要修改一次）
两个特殊字符“-”不会对应
S位置“-”代表增字符
T位置“-”代表删字符
使扣分最少
dp[i][j]表示S的前i个位置和T的前j个位置对齐的最少得分
dp[i][j] = min(dp[i-1][j-1]+same(i,j), dp[i-1][j]+1, dp[i][j-1]+1)
dp[i-1][j-1]+same(i,j)对应S第i个字符和T的第j个字符对齐
dp[i-1][j]+1对应S第i个字符和“-”对齐，即删掉S中第i个字符
dp[i][j-1]+1对应T第j个字符和“-”对齐，即在S中加入该字符
初值
dp[0][j] = j, j>=0
dp[i][0] = i, i>=0
时间复杂度：O(len(S)*len(T))
空间优化：省掉一维
对每个i，正向循环j
注意保存dp[i-1][j-1]，因为j-1已经是新值
1 class Solution { 2 public: 3 /** 4 * @param word1 & word2: Two string. 5 * @return: The minimum number of steps. 6 */ 7 int minDistance(string word1, string word2) { 8 // write your code here 9 int m = word1.length(), n = word2.length(); 10 vector<vector<int> > dp(m + 1, vector<int>(n + 1)); 11 for (int i = 0; i <= m; ++i) { 12 for (int j = 0; j <= n; ++j) { 13 if ( i== 0 ) { 14 dp[i][j] = j; 15 } else if (j == 0) { 16 dp[i][j] = i; 17 } else { 18 dp[i][j] = min(dp[i - 1][j - 1] + ((word1[i - 1] == word2[j - 1])?0:1), 19 min(dp[i][j - 1] + 1, dp[i - 1][j] + 1) 20 ); 21 } 22 } 23 } 24 return dp[m][n]; 25 } 26 };
空间优化
1 class Solution { 2 public: 3 /** 4 * @param word1 & word2: Two string. 5 * @return: The minimum number of steps. 6 */ 7 int minDistance(string word1, string word2) { 8 // write your code here 9 int m = word1.length(), n = word2.length(); 10 // vector<vector<int> > dp(m + 1, vector<int>(n + 1)); 11 vector<int> dp(n + 1); 12 for (int i = 0; i <= m; ++i) { 13 int last; 14 for (int j = 0; j <= n; ++j) { 15 if ( i== 0 ) { 16 dp[j] = j; 17 } else if (j == 0) { 18 last = dp[j]; 19 dp[j] = i; 20 } else { 21 int tmp = dp[j]; 22 dp[j] = min(last + ((word1[i - 1] == word2[j - 1])?0:1), 23 min(dp[j - 1] + 1, dp[j] + 1) 24 ); 25 last = tmp; 26 } 27 } 28 } 29 return dp[n]; 30 } 31 };
本文转自ZH奶酪博客园博客，原文链接：http://www.cnblogs.com/CheeseZH/p/5006590.html，如需转载请自行联系原作者
