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

假设两个字符串分别是a和b。

dp[i][j]表示 所有将a[1~i]变成 b[1~j]的操作方式的最少次数。

对于状态dp[i][j]可以怎么划分呢？

从三个操作的角度考虑：

1） 删除操作：a的[1~i-1]==b的[1~j]，删除a中第i个字符，a[1~i]和b[1~j]就变成一样了==》f[i][j] = f[i-1][j]+1。

2) 添加操作：a的[1~i]==b的[1~j-1]，添加b[j]作为a中第i个字符，a[1~i]和b[1~j]就变成一样了==》f[i][j] = f[i][j-1]+1。

3） 修改操作：

3.1） 当前若有 a[i]==b[j]：不需要修改， ==》 f[i][j] = f[i-1][j-1]+0

3.2） 当前若有 a[i]!=b[j]： 需要修改a字符串或者b字符串，==》 f[i][j] = f[i-1][j-1]+1

四种情况 取最小值

#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;
const int N = 1010;
int dp[N][N];  //dp[i][j] 表示所有将s1[1~i] 变成 s2[1~j]的方式的最少操作次数
int main() {
    
    char s1[N];
    char s2[N];
    scanf("%s", s1+1);
    scanf("%s", s2+1);
    int n = strlen(s1+1);
    int m = strlen(s2+1);
    //printf("%d,%d\n",n, m);
    for(int i = 0;i<=n;i++){
        dp[i][0] = i;
    }
    for(int j = 0 ;j<=m;j++){
        dp[0][j] = j;
    }
    for(int i = 1; i<=n;i++)
    {
        for(int j = 1;j<=m;j++)
        {   
            dp[i][j] = min(dp[i-1][j]+1, dp[i][j-1]+1);
            //对于f(i,j)来说，当s1[i] == s2[j]，f(i,j) = min{ f(i,j), f(i-1, j-1)}，此时不需要操作+0
            if(s1[i] == s2[j]){
                dp[i][j] = min(dp[i][j], dp[i-1][j-1]);
            }else{
                dp[i][j] = min(dp[i][j], dp[i-1][j-1]+1);
            } 
        }
    }

    printf("%d",dp[n][m]);
    return 0;

}
// 64 位输出请用 printf("%lld")