题目描述
给定两个字符串A和B，现在要将A经过若干操作变为B，可进行的操作有：
删除–将字符串A中的某个字符删除。
插入–在字符串A的某个位置插入某个字符。
替换–将字符串A中的某个字符替换为另一个字符。
现在请你求出，将A变为B至少需要进行多少次操作。
思路 动态规划
-
dp[i][j]- 集合 ： 所有吧
a中的前i个字母变成b中前j个字母的集合的操作集合 - 属性 ： 所有操作中
操作次数最少的方案的操作数
- 集合 ： 所有吧
- 状态计算
以对a中的第i个字母操作不同划分- 在该字母之后添加
- 添加一个字母之后变得相同，说明没有添加前
a的前i个已经和b的前j-1个已经相同 - 即 ：
dp[i][j] = dp[i][j-1] + 1
- 添加一个字母之后变得相同，说明没有添加前
- 删除该字母
- 删除该字母之后变得相同，说明没有删除前
a中前i-1已经和b的前j个已经相同 - 即 ：
dp[i][j] = dp[i-1][j] + 1
- 删除该字母之后变得相同，说明没有删除前
- 替换该字母
- 替换说明对应结尾字母不同，则看倒数第二个
- 即：
dp[i][j] = dp[i-1][j-1] + 1
- 啥也不做
- 对应结尾字母相同，直接比较倒数第二个
- 即：
dp[i][j] = dp[i-1][j-1]
- 在该字母之后添加
#include <iostream>
#include <string>
#include <vector>
using namespace std;
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];
}
int main(){
int a, b;
string s1, s2;
cin >> a >> s1 >> b >> s2;
cout << leastEdit(s1, s2);
return 0;
}
