目录
题目描述
输入格式:
输出格式:
输入样例:
输出样例:
解题思路：
代码实现：
题目描述
设A和B是2个字符串。要用最少的字符操作将字符串A转换为字符串B。这里所说的字符操作包括 (1)删除一个字符； (2)插入一个字符； (3)将一个字符改为另一个字符。 将字符串A变换为字符串B所用的最少字符操作数称为字符串A到 B的编辑距离，记为d(A,B)。 对于给定的字符串A和字符串B，计算其编辑距离 d(A,B)。
输入格式:
第一行是字符串A，文件的第二行是字符串B。
提示：字符串长度不超过2000个字符。
输出格式:
输出编辑距离d(A,B)
输入样例:
在这里给出一组输入。例如：
fxpimu xwrs
输出样例:
在这里给出相应的输出。例如：
5
简单来说求A，B的编辑距离，其实是求让A字符串与B字符串相等的最小操作次数。
解题思路：
线性动态规划，遍历所有情况
分为四种情况
1、无需变动即能保证当前匹配的两个字符串相等
2、匹配的字符串长度相同，当前位置的字符不同，通过替换一个字符串中的字符即可使两个字符串相同
3、A字符串比B字符串少一个字符，为了达成匹配，可以通过增加一个字符来达成匹配
4、A字符串比B字符串多一个字符，为了达成匹配，可以通过删除一个字符来达成匹配
或许可以换一种思考，要使得两个字符串长度相同且匹配，可以从四个方向走过来
四个方向分别为上述的四种情况。
代码实现：
#include<iostream> using namespace std; const int N=1e4+5;//用于初始化数组长度 int dp[N][N]; int main() {int n,m;string s1,s2;cin>>s1>>s2;n=s1.length();//计算n字符串的长度m=s2.length();//计算m字符串的长度for(int i=1;i<=n;i++){dp[i][0]=i;//s1中前i个字符跟s2中0个匹配，可以使用删除操作，删除i次，s1中刚好为0，达成匹配}for(int i=1;i<=m;i++){dp[0][i]=i;//s1中0个字符跟s2中前i个字符匹配，可以使用插入操作，插入i次，s1中刚好为i，达成匹配}for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){dp[i][j]=min(dp[i-1][j],dp[i][j-1])+1;//进行删和增的操作，当匹配到前i-1个和前j个匹配时可进行增加一个到i达到匹配，同理当前i个和前j-1个匹配时可以删除一个i达到匹配//进行改的操作if(s1[i-1]==s2[j-1])dp[i][j]=min(dp[i][j],dp[i-1][j-1]);//当前匹配成功，前一次匹配次数进行比较else dp[i][j]=min(dp[i][j],dp[i-1][j-1]+1);//匹配失败，前一次匹配操作次数+1进行比较}}cout<<dp[n][m]; }