网站建设专家论证会_设计网页作业_企拓客app骗局_百度商家平台

给定两个字符串 AA 和 BB，现在要将 AA 经过若干操作变为 BB，可进行的操作有：

1. 删除–将字符串 AA 中的某个字符删除。
2. 插入–在字符串 AA 的某个位置插入某个字符。
3. 替换–将字符串 AA 中的某个字符替换为另一个字符。

现在请你求出，将 AA 变为 BB 至少需要进行多少次操作。

输入格式

第一行包含整数 nn，表示字符串 AA 的长度。

第二行包含一个长度为 nn 的字符串 AA。

第三行包含整数 mm，表示字符串 BB 的长度。

第四行包含一个长度为 mm 的字符串 BB。

字符串中均只包含大小写字母。

输出格式

输出一个整数，表示最少操作次数。

数据范围

1≤n,m≤10001≤n,m≤1000

输入样例：

10
AGTCTGACGC
11
AGTAAGTAGGC

输出样例：

4

思路：

        作为经典DP问题，这一题也是用闫氏DP分析法。

        1.状态表示：

                集合：将字符串A的前i位变成字符串B的前j位的操作方式（f[i][j]）

                属性：操作数量最小值

        2.状态计算：

                第一种情况，删除。如果需要删除，就说明A字符串的第i位删掉后，能和字符串B完全匹配。而A的前i-1位与B的j为相匹配的操作次数为f[i-1][j]，在这个基础上加一次操作数量就是f[i][j]。

                第二种情况，增加。与第一种情况类似，但是A是比B少一位。因此A的前i位与B的前j-1位是完全匹配的。（f[i][j-1]）在这个基础上加一就是f[i][j]。

                第三种情况，替换。这种情况也需要分类讨论：1.如果A的第i位与B第j位相同，则不用调换，那么f[i][j]就等于f[i-1][j-1].2.如果不相同，那么就是f[i-1][j-1]+1，因为A前i-1和B前j-1肯定是完全匹配的。

        在代码中还要记得初始化i或j为0的情况，如f[i][0]就是i要删除全部i位，就初始化为i。而f[0][j]就是要增加j位，因此初始化为j。

        那么，代码就是：

        

int leastEdit(string a, string b){int m = a.size(), n = b.size();vector<vector<int>> dp(m+1, vector<int>(n+1));for(int i = 0; i <= m; i++) dp[i][0] = i;for(int i = 0; i <= n; i++) dp[0][i] = i;for(int i = 1; i <= m; i++){for(int j = 1; j <= n; j++){dp[i][j] = min(dp[i][j - 1], dp[i - 1][j]) + 1;  // 添加 和 删除 dp[i][j] = min(dp[i][j], dp[i-1][j-1] + (a[i - 1] != b[j - 1])); // 替换和 啥也不做}}return dp[m][n];
}作者：jasonlin
链接：https://www.acwing.com/solution/content/10499/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。