一、解题思路
与\(LCS\)（最长公共子序列）问题的状态表示是很接近的。
（1）集合划分
\(f[i,j]\)含义：\(a[1..i]\)变成\(b[1..j]\)的操作步数。
动态规划，就是不断的进行状态转移，并在转移过程中进行判断。因为要求是：两个字符串的最短编辑距离，我们不知道最短编辑距离是多少，就希望知道最终的状态是从哪些状态转移过来，前面的状态可以通过增加、删除、修改转移过来。如果我们能从小到大，将每个可能的状态描述出来，就不怕迁移了~
如何描述每个状态呢？当然是讨论\(a,b\)字符串的每一个子串，每一个子串的编辑距离可以算出来的话，那么最终的编辑距离肯定也就出来了。
（2）属性
操作数的最小值，\(min\)。
（3）状态计算
按题意划分为删除，增加，修改三种情况
一、删除
如果\(a[i]\)通过删除操作，可以达到\(b[j]\)一样的状态，那么最后的一步去掉第\(i\)个字符，也就是说\(a[i-1]\)之前的字符串可以通过\(f[i-1][j]\)步可以转化为\(b[j]\),那么加上删除的动作，就是：\(f[i][j]=f[i-1][j]+1\)
二、增加
如果\(a[i]\)通过增加操作，可以达到\(b[j]\)一样的状态，那么就意味着在\(a[i]\)通过\(f[i][j-1]\)步达到\(b[j-1]\)状态。也就是:\(f[i][j]=f[i][j-1]+1\)
三、修改
如果\(a[i]=b[j]\)是不需要进行修改的，就是\(f[i,j]=f[i-1,j-1]\)
如果\(a[i]!=b[j]\)是需要进行修改的，就是\(f[i,j]=f[i-1,j-1]+1\)
四、综合
\(f[i][j] = min(f[i-1][j]+1,f[i][j-1]+1,f[i-1][j-1]+(a[i] == b[j]?0:1))\);
五、初始化
细节问题：初始化怎么搞
先考虑有哪些初始化嘛
1.你看看在\(for\)遍历的时候需要用到的但是你事先没有的,（往往就是什么\(0\)啊\(1\)啊之类的）就要预处理
2.如果要找\(min\)的话别忘了\(INF\),要找有负数的max的话别忘了\(-INF\)
\(ok\),对应的：
-
\(f[0][i]\):如果\(a\)初始长度就是\(0\)，那么只能用插入操作让它变成\(b\)
\(f[i][0]\)同样地，如果\(b\)的长度是\(0\)，那么\(a\)只能用删除操作让它变成\(b\)
-
\(f[i][j]\) = \(INF\) 虽说这里没有用到，但是把考虑到的边界都写上还是保险
二、实现代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
int n, m;
char a[N], b[N];
int f[N][N];
// 最短编辑距离
int main() {
//优化输入
ios::sync_with_stdio(false);
cin >> n >> (a + 1) >> m >> (b + 1);
//这个初始化牛X啊！
for (int i = 0; i <= m; i++) f[0][i] = i;
for (int i = 0; i <= n; i++) f[i][0] = i;
//遍历所有可能性
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]);
else f[i][j] = min(f[i][j], f[i - 1][j - 1] + 1);
}
printf("%d\n", f[n][m]);
return 0;
}