最短编辑距离
原题链接： 72. 编辑距离 - 力扣（LeetCode）
https://leetcode.cn/problems/edit-distance/description/
状态表示f[i][j]：
- 集合：所有将
a[1:i]变成b[1:j]的操作方式 - 属性：Min
状态计算：
if (a[i] == b[j])f[i][j] = f[i - 1][j - 1];
else f[i][j] = min(f[i - 1][j] + 1, f[i][j - 1] + 1, f[i - 1][j - 1] + 1);划分一：a[i]与b[j]相等，不需要操作
划分二：a[i]与b[j]不等，需要增删改
- 如果进行插入操作，说明
a[]插入之后完全匹配 - 如果进行删除操作，说明
a[]删除之后完全匹配 - 如果进行修改操作，说明
a[]修改之后完全匹配
划分二的情况1：插入后完全匹配，说明插入之前，经过多次编辑后的a[]与b[1:j-1]完全匹配，a[]后插入的是b[j]。f[i][j]的值是，所有将a[1:i]变成b[1:j]的最短编辑次数。情况1发生时，a[]已经经过了多次编辑，此时的数组已经被修改成b[1:j-1]。此时的情况，不是a[1:i]与b[1:j-1]完全匹配，而是，将a[1:i]经过f[i][j-1]次编辑后，变成了b[1:j-1]，在经过一次插入操作后，将b[j]插入到a[]后，可以变成b[1:j]。此时，a[1:i]经过b[1:j-1]+1次编辑后得到了b[1:j]，根据状态表示f[i][j]的定义，a[1:i]经过f[i][j]次编辑后得到了b[1:j]。得到状态转移方程：f[i][j] = f[i][j-1]+1
划分二的情况2：删除后完全匹配，说明删除之前，经过多次编辑后的a[]的前j个元素与b[1:j]完全匹配。只有长度为j+1，才能在删除最后一个元素之后与长度为j的b[]完全匹配。最后一步操作为删除最后一个元素，这个元素就是a[i]，因为增改操作在结尾添加一个不匹配的元素是无意义的。多次编辑后的a[]的前j个元素，来源于a[i-1]，经过多次编辑后于b[1:j]完全匹配，最短编辑距离根据定义为f[i-1][j]。状态源a[1:i]较a[1:i-1]在结尾多了一个a[i]，经过f[i-1][j]次编辑，再加一次删除a[i]的操作，就可以与b[1:j]完全匹配，总的操作次数为f[i-1][j]+1，根据状态表示f[i][j]的定义，a[1:i]经过f[i][j]次编辑后得到了b[1:j]。得到状态转移方程：f[i][j] = f[i-1][j]+1
划分二的情况3：修改后完全匹配，说明多次编辑后的a[]的前j个元素与b[1:j-1]完全匹配。前j个元素来源于a[i-1]，经过多次编辑后于b[1:j-1]完全匹配，最短编辑距离根据定义为f[i-1][j-1]。在经过一次修改操作后，将多次编辑后的a[]的第j的元素修改为b[j]，就可以与b[1:j]完全匹配，总的操作次数为f[i-1][j-1]+1。得到状态转移方程：f[i][j] = f[i-1][j-1]+1
由于集合划分的依据是a[]变成b[1:j]的最后一步，当进入划分二时，3种情况都有可能，3种情况作为划分二的划分。
#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() {
cin >> n >> a + 1;
cin >> m >> b + 1;
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++) {
if (a[i] == b[j])f[i][j] = f[i - 1][j - 1];
else f[i][j] = min(min(f[i - 1][j] + 1, f[i][j - 1] + 1), f[i - 1][j - 1] + 1);
}
cout << f[n][m];
return 0;
}