A21197.编辑距离 正经题解

这是本人第二篇题解~

这道题刚好对标 CSP-J 2023 第一轮

程序采用二维 DP 求解，(dp[i][j]) 表示把 s1 前 i 个字符变成 s2 前 j 个字符的最小代价。

状态转移

状态转移时分两种情况
设当前比较字符：(a = s_1[i-1], b = s_2[j-1])

情况 1：(a == b)

两个字符相等，无需任何操作，直接继承前面结果：
(dp[i][j] = dp[i-1][j-1])

情况 2：(a ≠ b)，三种操作取最小值

删除 (s1) 当前字符：(dp[i-1][j] + 1)
在 (s1) 插入匹配 (s2) 当前字符：(dp[i][j-1] + 1)
替换当前字符：(dp[i-1][j-1] + 1)

(dp[i][j] = \min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1)

AC代码如下：

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

int dp[1010][1010];

int min(int a, int b, int c){
    return min(min(a, b), c);
}

int work(string a, string b){
    int m=a.size();
    int n=b.size();
    for(int i=0; i<=m; i++){
        for(int j=0; j<=n; j++){
            if(i==0) dp[i][j]=j;
            else if(j==0) dp[i][j]=i;
            else if(a[i-1]==b[j-1]) dp[i][j]=dp[i-1][j-1];
            else dp[i][j] = 1+min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]);
        }
    }
    
    return dp[m][n];
}

int main(){
    string a, b;
    cin >> a >> b;
    cout << work(a, b);
    return 0;
}

时间复杂度：(O(nm))，n、m 为两字符串长度，双重循环遍历 DP 表
空间复杂度：(O(nm))，二维数组存储 DP；可滚动数组优化至 (O(\min(n,m)))

求关注~