C++,动态规划，力扣官方解法

D[i][j] 表示 A 的前 i 个字母和 B 的前 j 个字母之间的编辑距离。 本质不同的操作实际上只有三种：

1. 在单词 A 中插入一个字符；
2. 在单词 B 中插入一个字符；
3. 修改单词 A 的一个字符。 特别地，如果 A 的第 i 个字符和 B 的第 j 个字符原本就相同，那么我们实际上不需要进行修改操作。在这种情况下，D[i][j] 最小可以为 D[i-1][j-1]。

作者：LeetCode-Solution 链接：https://leetcode-cn.com/problems/edit-distance/solution/bian-ji-ju-chi-by-leetcode-solution/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

#include <string>
#include <algorithm>
#include <iostream>
using namespace std;
int minDistance(const string& word1,const string& word2) {
int n = word1.length();
int m = word2.length();

// 有一个字符串为空串
if (n * m == 0) return n + m;

// DP 数组
int D[n + 1][m + 1];

// 边界状态初始化
for (int i = 0; i < n + 1; i++) {
D[i][0] = i;
}
for (int j = 0; j < m + 1; j++) {
D[0][j] = j;
}

// 计算所有 DP 值
for (int i = 1; i < n + 1; i++) {
for (int j = 1; j < m + 1; j++) {
int left = D[i - 1][j] + 1;
int down = D[i][j - 1] + 1;
int left_down = D[i - 1][j - 1];
if (word1[i - 1] != word2[j - 1]) left_down += 1;
D[i][j] = min(left, min(down, left_down));
}
}
return D[n][m];
}
int main(){
string sA,sB;
while(cin>>sA>>sB){
cout<<minDistance(sA, sB)<<endl;
}
}