题目：编辑距离
网址：https://www.luogu.com.cn/problem/P2758
题目描述
设A和B是两个字符串。我们要用最少的字符操作次数，将字符串A转换为字符串B。这里所说的字符操作共有三种：
1、删除一个字符；
2、插入一个字符；
3、将一个字符改为另一个字符；
！皆为小写字母！
输入格式
第一行为字符串A；第二行为字符串B；字符串A和B的长度均小于2000。
输出格式
只有一个正整数，为最少字符操作次数。
输入输出样例
输入
sfdqxbw
gfdgw
输出
4
这道题定义状态dp[i, j]代表考虑字符串A前i位，字符串B前j位最少操作数。
不难想到：插入和删除是等价的。
当插入（或删除）时，dp[i, j] = min(dp[i - 1, j] + 1, dp[i, j - 1] + 1)；当替换时，有：dp[i, j] = dp[i - 1, j - 1] + 1，由于字符a[i]及b[j]可能相同，不必再次替换；
代码如下：
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;
const int maxn = 2000 + 5;
int na, nb, dp[maxn][maxn];
char a[maxn], b[maxn];
int main()
{
scanf("%s %s", (a + 1), (b + 1));
na = strlen(a + 1), nb = strlen(b + 1);
//初始化
//dp[0, 0] = 0, dp[i, 0] = i, dp[0, j] = j | 1 <= i <= na, 1 <= j <= nb
memset(dp, 0, sizeof(dp));
for(int i = 1; i <= na; ++ i) dp[i][0] = i;
for(int i = 1; i <= nb; ++ i) dp[0][i] = i;
for(int i = 1; i <= na; ++ i)
{
for(int j = 1; j <= nb; ++ j)
{
//因为插入和删除实际上是等价的
dp[i][j] = min(dp[i][j - 1], dp[i - 1][j]) + 1; //删除
if(a[i] == b[j]) dp[i][j] = min(dp[i][j], dp[i - 1][j - 1]);//替换
else dp[i][j] = min(dp[i - 1][j - 1] + 1, dp[i][j]);
}
}
printf("%d
", dp[na][nb]);//输出答案
return 0;
}