AcWing 902. 最短编辑距离（线性DP）

题目链接

https://www.acwing.com/problem/content/description/904/

思路

因为题目中有三种操作A字符串的方法：

• 删除A中一个元素
• 给A增加任意元素
• 将A中任意位置替换成某个元素

我们定义 f [ i ] [ j ] f[i][j] f[i][j]表示的是字符串A从 [ 1 , i ] [1,i] [1,i]和字符串B [ 1 , j ] [1,j] [1,j]完成匹配需要的最少操作次数，那么我们考虑最A字符串的最后一个位置的操作情况

• 如果A最后一个位置是删除操作，说明从A字符串中 [ 1 , i − 1 ] [1,i-1] [1,i−1]的部分和B字符串中 [ 1 , j ] [1,j] [1,j]的部分匹配的最小值转移过来，即 f [ i ] [ j ] = f [ i − 1 ] [ j ] + 1 f[i][j] = f[i-1][j]+1 f[i][j]=f[i−1][j]+1
• 如果A最后一个位置是删除操作，说明从A字符串中 [ 1 , i ] [1,i] [1,i]的部分和B字符串中 [ 1 , j − 1 ] [1,j-1] [1,j−1]的部分匹配的最小值转移过来，即 f [ i ] [ j ] = f [ i ] [ j − 1 ] + 1 f[i][j] = f[i][j-1]+1 f[i][j]=f[i][j−1]+1
• 如果A最后一个位置是替换操作，说明A字符串中 [ 1 , i − 1 ] [1,i-1] [1,i−1]的部分和B字符串中 [ 1 , j − 1 ] [1,j-1] [1,j−1]的部分匹配的最小值转移过来，此时我们需要判断 a [ i ] a[i] a[i]和 b [ j ] b[j] b[j]是否相等，如果相等的话就直接转移否则则需要加上一个修改操作： f [ i ] [ j ] = f [ i − 1 ] [ j − 1 ] + 1 f[i][j]=f[i-1][j-1] + 1 f[i][j]=f[i−1][j−1]+1(如果需要修改的话)

详情请看代码：

代码

#include
using namespace std;

const int N = 1000 + 10;
int n,m;
int f[N][N];

char a[N],b[N];

int main()
{
    cin>>n>>(a+1);
    cin>>m>>(b+1);
    for(int i = 0;i