A21197.编辑距离题解

依旧模板题。

/*
定义：dp[i][j]:对s的前i个字符和t前j个字符的最小的编辑距离。
分解：考虑第i个字符在前j个元素中的编辑距离。
    1）删除操作：删除s的第i个：dp[i] = dp[i - 1][j] + 1;
    2）插入操作：在a的第i个后插入b[j]：dp[i] = dp[i][j - 1] + 1;
    3）替换操作：将s的第i个元素替换成t[j]：dp[i] = dp[i - 1][j - 1] + 1;
    4）s的第i个s字符与第j个字符相等：dp[i][j] = dp[i - 1][j - 1];
边界：
    1)删除：dp[i][0] = i;
    2)删除：dp[0][j] = j;
*/
#include <bits/stdc++.h>
using namespace std;
string s,t;
int dp[2005][2005];
int main()
{
    cin >> s >> t;
    int n = s.size(),m = t.size();
    for(int i = 1;i <= n;i ++)
    {
        dp[i][0] = i;
    }
    for(int i = 1;i <= m;i ++)
    {
        dp[0][i] = i;
    }
    for(int i = 1;i <= n;i ++)
    {
        for(int j = 1;j <= m;j ++)
        {
            if(s[i - 1] == t[j - 1]) dp[i][j] = dp[i - 1][j - 1];
            else dp[i][j] = min({dp[i - 1][j] ,dp[i][j - 1] ,dp[i - 1][j - 1] }) + 1;
        }
    }
    cout << dp[n][m];
    return 0;
}

花了好久写的注释，有用请点个赞！！！