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

#include <climits>
#include <iostream>
#include <vector>
using namespace std;

//a 插入   b 删除    c替换
int min_edit_Distance(string s, string t ,int a,int b,int c)
{
    int n = s.length();
    int m = t.length();

    //dp[i][j]: s串前i个字符变成 t串的前j个字符所需要的最小代价
    //s[i-1] == t[j-1] 依赖dp[i-1][j-1]
    //
    // 1）s串前i-1个字符去搞定t串前j-1个字符（dp[i-1][j-1]）+替换代价c
    // 2）s串前i个字符去搞定t串的前j-1个字符（dp[i][j-1]） + 插入代价a
    // 3）直接把s串最后一个字符删了，让s串前i-1个字符去搞定t串前j个字符（dp[i-1][j]）+删除代价b

    //base ：第0行：s串0个字符去搞定t串 0....m个字符，直接插入就行
    //第0列：s串 0....n个字符 去搞定t串0个字符，直接删除就行

    vector<vector<int>> dp(n+1,vector<int>(m+1, INT_MAX));
    for (int i = 0; i<=n; ++i)
    {
        dp[i][0] = i*a;
    }

    for (int j = 1; j<=m; ++j)
    {
        dp[0][j] = j*b;
    }

    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 {
                int p1 = dp[i-1][j-1] + c;
                int p2 = dp[i][j-1] + a;
                int p3 = dp[i-1][j] + b;
                dp[i][j] = min(p1,min(p2,p3));
            }
        }
    }
    return dp[n][m];
}


int main() {
    string s,t;
    cin >> s >> t;

    cout << min_edit_Distance(s, t, 1, 1, 1);
}
// 64 位输出请用 printf("%lld")