1183 编辑距离

解题思想

/*
设本题的三个操作分别是删除del， 插入ins， 替换rep
dp[i][j] 表示串a的 0 –>i-1 变换到串b的0–>j-1 所需的最小编辑距离
则一共有四个决策：分别是
1.当串a与串b的最后一个字符相等时，即a[i-1] == b[j-1]
dp[i][j] = dp[i-1][j-1] ;
2.当不相等时
dp[i][j] = dp[i-1][j-1] + rep ;

3.a[0..i-1] 可以先编辑成a[0..i-2],即删除 字符a[i-1],即由a[0..i-2]编辑成b[0..j-1]
dp[i][j] = dp[i-1][j] + dec ;
总结就是串a多了一个字符，需要删除

4.a[0..i-1] 可以先编辑成 b[0..j-2] , 然后再将b[j-1]插入b[0..j-2]
dp[i][j] = dp[i][j-1] + ins;
总结就是，串a少一个字符，只能凑够串b的前n-1个字符，需要插入

*/

代码

#include<iostream>
#include<cstring>
using namespace std;

int main()
{
    string a, b;
    cin >> a >> b;
    int del = 1, rep = 1, ins = 1;
    int lena = a.length();
    int lenb = b.length();
    int dp[lena+1][lenb+1];
    dp[0][0] = 0;
    for(int i=0; i<lena+1; ++i)
        dp[i][0] = i*del;
    for(int j=0; j<lenb+1; ++j)
        dp[0][j] = j*ins;
    for(int i=1; i< lena+1; ++i)
        for(int j=1; j<lenb+1; ++j)
    {
        if(a[i-1] == b[j-1])
        {
            dp[i][j] = dp[i-1][j-1];
        }else
        {
            dp[i][j] = dp[i-1][j-1] + rep;

        }
        dp[i][j] = min(dp[i][j], dp[i-1][j]+del);
        dp[i][j] = min(dp[i][j], dp[i][j-1]+ins);
    }
    cout << dp[lena][lenb] <<endl;;
    return 0;
}