编辑距离

原题：902. 最短编辑距离 - AcWing题库

状态表示

a串的前 i 个与b串的前 j 个修改好的所有可能改法中的最少更改次数

状态计算

以最后一次更改分类：

• 删除 即删除第 i 个后，恰好修改好 这种情况说明 前 i-1 个与 前 j 个匹配，f[i][j] = f[i-1][j] + 1
• 增加 即增加第 i+1 个后，恰好改好 这说明 前 i 个与 j-1 个匹配 f[i][j] = f[i][j-1] + 1
• 修改 即修改第 i 个后改好 说明f[i][j] = f[i-1][j-1] + 1
• 匹配 a[i] == b[j] f[i][j] = f[i-1][j-1]

实现

//求最小记得初始化
	 for(int i = 0; i <= n; i ++)
        for(int j = 0; j <= m; j ++)
            f[i][j] = INF;
            
    //要按照分析处理特殊值
    //a的0位与b的i位匹配，只能是增加操作
    for(int i = 0; i <= m ; i ++)  f[0][i] = i;
    //a的i位与b的0位匹配，只能删除
    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);
            }
            
    
    cout << f[n][m] << endl;