//分类,对于最后一个数进行操作,分为三类,分别是删除操作、增加操作和替换操作
//删除操作如何表示?假设我们现在应该要执行的操作是删除操作,那么应该是f[i][j]=f[i-1][j]+1,为什么呢?
//因为如果要删除a中第i个字母的话,那么根据前面我们对于f[i][j]的定义不难推断出,a中的前i-1个字母应该和b中前j个字母是匹配的。(不然不会执行删除操作)
//所以我们进行删除操作的时候只需要在前一步的情况下加上1即可。
//增加操作如何表示?假设我们现在应该要执行增加操作,那么应该是f[i][j]=f[i][j-1]+1,.为什么呢?
//根据定义,我们是希望通过对于最后一步的操作来实现a中前i个字母和b中前j个字母相等。
//所以我们根据此定义可以推出,我们在没有执行增加操作之前,我们的a中的前i个字母是和b中前j-1个字母相等的。
//因为只有这样,我们做增加操作才能够达到我们的目的。
//最后一个,替换操作如何表示?假设我们现在应该要执行的操作是替换操作,那么我们应该考虑一个问题。
//什么问题呢?如果我们的最后一个字母a[i]等于a[j]的话,那我们就不需要进行操作了,所以此时f[i][j]=f[i-1][j-1]。
//如果a[i]不等于b[j],那么我们就要执行替换操作,那么和上面分析的思路一样。
//我们可以通过替换来达到我们所需要的“a中前i个字母和b中前j个字母一样“,那么根据这个定义,
//我们就可以推理出,我们a中前i-1个字母和b中前j-1个字母肯定是一样的,因为只有这样我们才能通过替换操作来达到我们的目的
//那么所有情况我们都分析出来了,接下来我们就可以尝试着写一些代码
C++ 代码
// 最短编辑距离.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//
#include<iostream>
#include<bits/stdc++.h>
using namespace std;
const int N = 1010;
char a[N], b[N];
int f[N][N] = {};//f[i][j]表示将a中前i个字母变得和b中前j个字母相同所需要的最小操作次数(思考步骤是关键步骤)
int n, m;
int main()
{
scanf("%d%s%d%s", &n,a+1,&m,b+1);
//接下来考虑一下初始化的问题,如果我们用a中0个字符去对应b中j个字符,那么我们就要进行j次增加操作,那么我们就要把
//f[0][j]=j,然后如果我们用a中i个字母去对应b中0个字符的话,我们就需要进行i次删除操作,也就是f[i][0]=i;
//这个的话大家可以根据前面我们对于f[i][j]的定义去理解一下,为什么是这样子初始化
for (int i = 0; i <= n; i++)//表示初始化用a中i个字母去对应b中j个字母
f[i][0] = i;
for (int j = 0; j <= m; j++)//表示初始化用a中0个字母去对应b中j个字母
f[0][j] = j;
for(int i=1;i<=n;i++)//初始化之后就可以直接套我们的状态转移方程了
for (int j = 1; j <= m; j++)
{
f[i][j] = min(f[i - 1][j] + 1, f[i][j - 1] + 1);//先转移前两种操作,删除和增加,因为这两种不需要额外的特判
if (a[i] != b[j])//对于第三种替换操进行特判操作
f[i][j] = min(f[i][j], f[i - 1][j - 1] + 1);
else
f[i][j] = min(f[i][j], f[i - 1][j - 1]);
}
printf("%d", f[n][m]);
return 0;
}
// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单
// 入门使用技巧:
// 1. 使用解决方案资源管理器窗口添加/管理文件
// 2. 使用团队资源管理器窗口连接到源代码管理
// 3. 使用输出窗口查看生成输出和其他消息
// 4. 使用错误列表窗口查看错误
// 5. 转到“项目”>“添加新项”以创建新的代码文件,或转到“项目”>“添加现有项”以将现有代码文件添加到项目
// 6. 将来,若要再次打开此项目,请转到“文件”>“打开”>“项目”并选择 .sln 文件