题意分析
给定字符串 $a,b$，有三种操作：
- 删除一个字符；
- 插入一个字符；
- 修改一个字符。
求至少需要多少次操作才能将 $a$ 转换为 $b$。
DP
状态设计
设 $dp_{i,j}$ 表示 $a$ 的前 $i$ 个字符转化为 $b$ 的前 $j$ 个字符的最少操作次数，即将 $a[1,i]$ 转化为 $b[1,j]$ 的最少操作次数。答案即 $dp_{lena,lenb}$，$lena$ 表示 $a$ 的长度，$lenb$ 同理。
状态转移
考虑三种操作如何转移 $dp_{i,j}$。
-
删除一个字符。
考虑删除 $a[1,i]$ 末尾的字符，则变为 $a[1,i-1]$，最小代价为 $dp_{i-1,j}$，有 $dp_{i,j}=dp_{i-1,j}+1$。
-
插入一个字符。
考虑插入到 $a[1,i]$ 的末尾。$a[1,i]$ 插入并转换后为 $b[1,j]$，那么考虑将 $a[1,i]$ 转化为 $b[1,j-1]$，有 $dp_{i,j}=dp_{i,j-1}+1$。
-
修改一个字符。
将末尾字符修改为相同，则有 $dp_{i,j}=dp_{i-1,j-1}+1$。
-
当 $a_i,b_j$ 相同时。
可以无需操作，此时有 $dp_{i,j}=dp_{i-1,j-1}$。
汇总，有：
\[dp_{i,j}= \begin{cases} \min(dp_{i-1,j},dp_{i,j-1},dp_{i-1,j-1})+1&a_i\ne b_j\\ \min(\min(dp_{i-1,j},dp_{i,j-1})+1,dp_{i-1,j-1})&a_i=b_j\\ \end{cases}\]即：
\[dp_{i,j}=\min(\min(dp_{i-1,j},dp_{i,j-1})+1,dp_{i-1,j-1}+[a_i\ne b_j])\]其中，$[a_i\ne b_j]$ 是艾弗森括号的表示，即当 $a_i\ne b_j$ 成立时为 $1$，否则为 $0$。
边界条件
\[dp_{i,0}=i\\ dp_{0,j}=j\]即全部删除。
AC 代码
时间复杂度：$\mathcal O\left(n^2\right)$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
//#include<bits/stdc++.h>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<iomanip>
#include<cstdio>
#include<string>
#include<vector>
#include<cmath>
#include<ctime>
#include<deque>
#include<queue>
#include<stack>
#include<list>
using namespace std;
constexpr const int N=2000;
char a[N+1+1],b[N+1+1],tmp[N+1+1];
int lena,lenb,dp[N+1][N+1];
int main(){
/*freopen("test.in","r",stdin);
freopen("test.out","w",stdout);*/
scanf("%s%s",a+1,b+1);
lena=strlen(a+1);lenb=strlen(b+1);
for(int i=1;i<=lena;i++){
dp[i][0]=i;
}
for(int j=1;j<=lenb;j++){
dp[0][j]=j;
}
for(int i=1;i<=lena;i++){
for(int j=1;j<=lenb;j++){
dp[i][j]=min(dp[i-1][j],dp[i][j-1])+1;
dp[i][j]=min(dp[i][j],dp[i-1][j-1]+(a[i]!=b[j]));
}
}
printf("%d\n",dp[lena][lenb]);
/*fclose(stdin);
fclose(stdout);*/
return 0;
}
