解析

当s[i - 1] == ss[j -1]时，编辑距离不变； 当s[i - 1] != ss[j - 1]时：

• 删除s：dp[i][j - 1] + 1；
• 插入ss：dp[i - 1][j - 1] + 1；
• 替换s or ss：dp[i - 1][j - 1] + 1;

Therefore, 只需取三个操作中的最小值即可；

代码

#include <iostream>
#include <string.h>
#define LL long long
using namespace std;
string s,ss;
int dp[2005][2005];
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
	cin >> s >> ss;
    int len1 = s.size();
    int len2 = ss.size();
    for(int i = 1;i <= len1;i++) dp[i][0] = i;
    for(int j = 1;j <= len2;j++) dp[0][j] = j;
    for(int i = 1;i <= len1;i++){
    	for(int j = 1;j <= len2;j++){
    		if(s[i-1] == ss[j-1]){
    			dp[i][j] = dp[i - 1][j - 1];
			}
			else dp[i][j] = min(min(dp[i][j - 1],dp[i - 1][j]),dp[i - 1][j - 1]) + 1;
		}
	}
	cout << dp[len1][len2];
    return 0;
    //cout << __cplusplus;
}
/*
來自中原一群夥伴
結盧東南山
塵緣難盡默對寒窗
龍珠合十在胸膛
秉承千年卓絕意志
潛修東南山
寧靜致遠風雨聲響
不絕如縷持香案
香火在雨中燒幾十個暑和寒
血脈相連一方苦行山
龍珠九轉十二金光
反指五嶽和三江
*/

有问题可以回复，谢谢。

^{不要关心我的注释}

#include <bits/stdc++.h>
using namespace std;

const int N = 2005;
int dp[N][N];

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	string a, b;
	cin >> a >> b;
	int n = a.length(), m = b.length();
	a = ' ' + a, b = ' ' + b;
	for (int i = 1; i <= n; i++) dp[i][0] = i;
	for (int j = 1; j <= m; j++) dp[0][j] = j;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			if (a[i] == b[j]) {
				dp[i][j] = dp[i - 1][j - 1];
			} else {
				dp[i][j] = min(min(dp[i][j - 1], dp[i - 1][j]), dp[i - 1][j - 1]) + 1;
			}
		}
	}
	cout << dp[n][m] << '\n';
	return 0;
}