给定两个字符串A和B，以及下列三种字符运算：
（1）删除一个字符（2）插入一个字符（3）将一个字符改写为另一个字符
设计算法求将A通过以上三种操作转换为B的最小次数
举例： “xy” => “xz”，只需要把 y 替换成 z，因此，最小编辑距离为 1。
“xyz” => “xy”，只需要删除 z ，请设计动态规划算法。
提示
- 如果 a[m] === b[n]，那么问题转化为求解：a[1]a[2]…a[m-1] => b[1]b[2]…b[n-1] 的最小编辑距离，因此 d[m][n] === d[m-1][n-1]。比如，“xyz” => “pqz” 的最小编辑距离等于 “xy” =>“pq” 的最小编辑距离。
- 如果 a[m] !== b[n]，又分为三种情况： • 比如，“xyz” => “efg” 的最小编辑距离等于 “xy” => “efg” 的最小编辑距离 + 1（因为允许插入操作，插入一个 “z”），抽象的描述便是 d[m][n] === d[m-1][n] + 1。
• 比如，“xyz” => “efg” 的最小编辑距离等于 “xyzg” => “efg” 的最小编辑距离 +1，且因为最后一个字符都是 “g”，根据第一个判断条件，可以再等于 “xyz” => “ef” 的最小编辑距离 +1，因此，得到结论：“xyz” => “efg” 的最小编辑距离等于 “xyz” => “ef” 的最小编辑距离 +1，抽象的描述便是：d\[m\]\[n\] === d\[m\]\[n-1\] + 1。 • 比如，“xyz” => “efg” 的最小编辑距离等于"xyg" => “efg” 的最小编辑距离 + 1（因为允许替换操作，可以把 “g” 换成 “z”），再等于 “xy” => “ef”
的编辑距离 + 1（根据第一个判断条件），抽象的描述便是： d\[m\]\[n\] === d\[m-1\]\[n-1\] + 1。
上述三种情况都有可能出现，因此，取其中的最小值便是整体上的最小编辑距离。
- 如果 a 的长度为 0，那么 a => b 的最小编辑距离为 b 的长度；反过来，如果 b 的长度为 0，那么 a => b 的最小编辑距离为 a 的长度。
代码
#include<bits/stdc++.h>
//#include
//#include <string.h>
//#include
//#include //min()包含头文件
using namespace std;
int main(){
char str1[1025],str2[1025];//长度不超过1024,长度最小要声明为1024+1,因为字符串末尾有空字符。
int n,m,temp;
while(cin>>str1>>str2){//循环输入两个字符串
m=strlen(str1);
n=strlen(str2);
vector<vector > dp(m+1,vector(n+1,0));//生成一个m+1行n+1列的二维矩阵记录当前的状态值
//初始化
for(int i=1;i<=m;i++)//dp[i][0]=i，例如dp[2][0]表示一个长度为2的字符串str1与一个空字符串str2的最小编辑距离为2（即依次将str1中的字符添加到str2中）
dp[i][0]=i;
for(int j=0;j<=n;j++)//dp[0][j]=j，例如dp[0][1]表示一个空字符串str1与一个长度为1的字符串str2的最小编辑距离为1（即依次将str2中的字符添加到str1中）
dp[0][j]=j;
dp[0][0]=0;//空字符串与空字符串之间的最小编辑距离为0
for(int i=1;i<=m;i++){
for(int j=1;j<=n;j++){
if(str2[j-1]==str1[i-1])//注意：字符串str1和str2中的索引是从0开始的，而1<=i<=m,1<=j<=n,所以这里的i和j要减1
dp[i][j]=dp[i-1][j-1];
else{
temp=min(dp[i][j-1],dp[i-1][j]);
dp[i][j]=min(temp,dp[i-1][j-1])+1;
}
}
}
cout<<dp[m][n]<<endl;//最终的dp[m][n]为两字符串之间的最小编辑距离
}
return 0;
}
运行
自我介绍一下，小编13年上海交大毕业，曾经在小公司待过，也去过华为、OPPO等大厂，18年进入阿里一直到现在。
深知大多数前端工程师，想要提升技能，往往是自己摸索成长或者是报班学习，但对于培训机构动则几千的学费，着实压力不小。自己不成体系的自学效果低效又漫长，而且极易碰到天花板技术停滞不前！
因此收集整理了一份《2024年Web前端开发全套学习资料》，初衷也很简单，就是希望能够帮助到想自学提升又不知道该从何学起的朋友，同时减轻大家的负担。
既有适合小白学习的零基础资料，也有适合3年以上经验的小伙伴深入学习提升的进阶课程，基本涵盖了95%以上前端开发知识点，真正体系化！
由于文件比较大，这里只是将部分目录截图出来，每个节点里面都包含大厂面经、学习笔记、源码讲义、实战项目、讲解视频，并且会持续更新！
如果你觉得这些内容对你有帮助，可以扫码获取！！（备注：前端）
最后
基础知识是前端一面必问的，如果你在基础知识这一块翻车了，就算你框架玩的再6，webpack、git、node学习的再好也无济于事，因为对方就不会再给你展示的机会，千万不要因为基础错过了自己心怡的公司。前端的基础知识杂且多，并不是理解就ok了，有些是真的要去记。当然了我们是牛x的前端工程师，每天像背英语单词一样去背知识点就没必要了，只要平时工作中多注意总结，面试前端刷下题目就可以了。
什么？你问面试题资料在哪里，这不是就在你眼前吗（滑稽文章来源：https://www.toymoban.com/news/detail-857663.html
，千万不要因为基础错过了自己心怡的公司。前端的基础知识杂且多，并不是理解就ok了，有些是真的要去记。当然了我们是牛x的前端工程师，每天像背英语单词一样去背知识点就没必要了，只要平时工作中多注意总结，面试前端刷下题目就可以了。
什么？你问面试题资料在哪里，这不是就在你眼前吗（滑稽
资料领取方式：戳这里获取文章来源地址https://www.toymoban.com/news/detail-857663.html
到了这里，关于【动态规划----“最小编辑距离”问题（C++解决）】的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
