题目

给定两个字符串 A 和 B，现在要将 A 经过若干操作变为 B，可进行的操作有：
1.删除–将字符串 A中的某个字符删除。
2.插入–在字符串 A 的某个位置插入某个字符。
3.替换–将字符串 A 中的某个字符替换为另一个字符。
现在请你求出，将 A变为 B至少需要进行多少次操作。

输入格式

第一行包含整数 n，表示字符串 A 的长度。
第二行包含一个长度为 n的字符串 A。
第三行包含整数 m，表示字符串 B 的长度。
第四行包含一个长度为 m 的字符串 B。
字符串中均只包含大小写字母。

输出格式

输出一个整数，表示最少操作次数

数据范围

1≤n,m≤1000

非常标准的dp问题，拥有三种状态并从三种状态中判断操作的最大或者最小值
用f[][]数组的两个维度表示 AB连个字符串的最小值信息，通过分三类讨论得到最终结果

状态方程分析

定义状态数组f[i][j] : 存储将A中前i个字符转换为B中前j个字符的最小操作数的集合
属性：取三种操作中操作数最小的方案集合
1)删除操作：把a[i]删掉之后a[1-i]和b[1-j]匹配 所以之前要先做到a[1-(i-1)]和b[1-j]匹配 f[i-1][j] + 1
2)插入操作：插入之后a[i]与b[j]完全匹配，所以插入的就是b[j] 那填之前a[1-i]和b[1-(j-1)]匹配 f[i][j-1] + 1
3)替换操作：把a[i]改成b[j]之后想要a[1-i]与b[1-j]匹配 那么修改这一位之前，a[1~(i-1)]应该与b[1~(j-1)]匹配 f[i-1][j-1] + 1
但是如果本来a[i]与b[j]这一位上就相等，那么不用改，即 f[i-1][j-1]

dp代码

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

const int N = 1010;
int n,m;
char a[N],b[N];
int f[N][N];

int main()
{
    //scanf读取int 和  char数组
    scanf("%d%s",&n,a+1);
    scanf("%d%s",&m,b+1);

    //初始化数组
    //A为0 B为i A->B的编辑距离就是B的个数（插入操作）
    for(int i = 0;i <= m;i++) f[0][i] = i;
    //A为i B为0 A->B的编辑距离就是A的个数（删除操作）
    for(int i = 0;i <= n;i++) f[i][0] = i;
    
    //0已经被初始化dp从1开始
    for(int i = 1;i <= n;i++)
    {
        for(int j = 1;j <= m;j++)
        {
            //先对删除和插入操作取min
            f[i][j] = min(f[i-1][j] + 1,f[i][j - 1] + 1);
            //替换操作存在判断条件 a[i] == b[j]
            if(a[i] == b[j]) f[i][j] = min(f[i][j],f[i - 1][j - 1]);
            else f[i][j] = min(f[i][j],f[i - 1][j - 1] + 1);
        }
    }
    cout << f[n][m];
    return 0;
}