acwing899. 编辑距离

状态表示：两个字符串，二维数组f[i][j]

集合：所有将a[1~i]变成b[1~j]的操作方式

属性：最小值

分类：三种，删，增，改。

时间复杂度：状态数：3，转移数：O(n2)，一共，O(n2)

动态规划的状态转移和分类，通常从最后一步去考虑！！

#include<iostream>
#include <algorithm>
using namespace std;

const int N = 1010;
int n, m;
char a[N], b[N];
int f[N][N];

int main(){
    scanf("%d%s", &n, a + 1);//字符串下标从1开始
    scanf("%d%s", &m, b + 1);
    
    for(int i = 0; i <= m; i ++ ) f[0][i] = i;//a的前0个字母和b的前i个字母匹配，需要增加i次
    for(int i = 0; i <= n; i ++ ) f[i][0] = i;//b的前0个字母和a的前i个字母匹配，需要删除i次
    
    for(int i = 1; i <= n; i ++ )
        for(int j = 1; j <= m; j ++ )//坐标含0的都已经初始化完了，从1开始
        {
            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]);//把a的前n个字母变成b的前m个字母，答案即f[n][m]
    return 0;
}