题解 | #计算字符串的编辑距离#

#include <iostream>
using namespace std;
const int N = 1e3 + 5;
string s1;
string s2;
int p[N][N];
int dp[N][N]; //dp[i][j]：s1前i个字母到s2前j个字母的编辑距离
int dfs(int x, int y) {
    int res = 1e9;
    if (dp[x][y]) return dp[x][y];
    if (x == 0) return dp[x][y] = y;
    if (y == 0) return dp[x][y] = x;
    if (s1[x] == s2[y]) res = min(res, dfs(x - 1, y - 1)); //不动
    else res = min(res, dfs(x - 1, y - 1) + 1); //改
    res = min(res, dfs(x - 1, y) + 1); //删
    res = min(res, dfs(x, y - 1) + 1); //增
    return dp[x][y] = res;
}
int main() {
    cin >> s1 >> s2;
    s1 = ' ' + s1;
    s2 = ' ' + s2;
    cout << dfs(s1.size() - 1, s2.size() - 1) << endl;
}