这道题也是leetcode72，
注意代码中的i，j代表第几个字符，0表示空串，所以比较word1的第i个与word2的第j个是
if(word1[i-1] == word2[j-1])
int minDistance(string word1, string word2) { int m = word1.length(), n = word2.length(); for(int i = 0;i <= m;i++) d[i][0] = i; for(int i = 0;i <= n;i++) d[0][i] = i; for(int i = 1;i <= m;i++) for(int j = 1;j <= n;j++) { if(word1[i-1] == word2[j-1]) d[i][j] = d[i-1][j-1]; else{ d[i][j] = min(d[i-1][j-1], min(d[i-1][j], d[i][j-1])) + 1; } } return d[m][n]; }
还可以用滚动数组，去掉第一维节省空间（不会减少时间）
参考链接：《算法设计与分析》-董老师的PPT
原文：https://www.cnblogs.com/lfri/p/12441517.html