洛谷题单指南-动态规划2-P2758 编辑距离

原题链接：https://www.luogu.com.cn/problem/P2758

题意解读：对a字符串最少操作几次可以变成b字符串，看似无从下手，可以从内部递推关系着手。

解题思路：

设dp[i][j]表示将a字符串1~i变成b字符串1~j的最少操作次数，字符串下标从1开始。

如何思考递推？可以从最后一步为切入点！最后一步对a[i]的操作有三种可能：

1、插入操作

在a[i]后面插入一个元素使得a等于b，前提是a的1~i和b的1~j-1已经相等，所以有dp[i][j] = dp[i][j-1] + 1

2、删除操作

把a[i]删除使得a等于b，前提是a的1~i-1已经与b的1~j相等，所以有dp[i][j] = dp[i-1][j] + 1

3、修改操作

a[i] != b[j]时，如果只把a[i]修改为b[j]就可以使得a等于b，前提是a的1~i-1已经与b的1~j-1相等，所以有dp[i][j] = dp[i-1][j-1] + 1

a[i] == b[j]时，最后一步都不需要修改，只要a的1~i-1已经与b的1~j-1相等就可以，所以有dp[i][j] = dp[i-1][j-1]

以上情况取min即可求得最少编辑次数。

注意：对dp[][]进行初始化

所有dp[i][0]都应该初始化为i，因为a的1~i变成空需要删i次；

所有dp[0][j]都应该初始化为j，因为a从空到b的1~j需要插入j次。

100分代码：

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

string a, b;
int dp[2005][2005];

int main()
{
    cin >> a >> b;
    int m = a.size();
    int n = b.size();
    a = " " + a;
    b = " " + b;

    for(int i = 1; i <= m; i++) dp[i][0] = i; //把a前i个变成b前0个也就是""需要删i次
    for(int j = 1; j <= n; j++) dp[0][j] = j; //把a前0个变成b前j个要插入j次

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