彻底理解编辑距离问题edit distance-德赢Vwin官网网

给定两个字符串word1以及word2，返回将word1转为word2需要的最少步骤，在每一步中你可以针对字符串word1进行以下操作：

新增一个字符

删除一个字符

替换一个字符

假如word1是"horse"，word2是“ros”，那么你的程序需要返回3，也就是说将word1转为word2至少需要三个步骤：

将word1中的第一个字符h替换为字符r：horse -> rorse，此时word1变为rorse，word1与word2前两个字符相等

将word1中的第三个字符r删掉：rorse -> rose，此时word1变为rose，word1与word2的前三个字符相等

将word1中的最后一个字符删掉：rose -> ros，此时word1与word2相等。

想一想该怎样用动态规划解决这个问题。

选择与子问题

和之前的题目一样，你首先应该找出子问题是什么，子问题与原始问题的依赖关系是什么。

找出子问题的关键在于每一步的选择。

如果word1与word2的第一个字符相等，假设word1是hor、word2是hr，那么我们可以放心的排除掉两个字符串的第一个字符，即EditDistance("hor", "hr")一定等于EditDistance("or", "r")：

此时我们得到了一个子问题EditDistance("or", "r")，原始问题EditDistance("hor", "hr")的值等于该子问题。

真正有趣的是如果word1与word2的第一个字符不相等的情况，假设word1为“hor”，而word2为“ro”，此时根据该问题的规则针对word1的第一个字符有三种操作：

1，在word1的第一个字符前新增(Insert)一个字符r，此时word1变为rhor，由于此时word1 的第一个字符等于word2的第一个字符，可以放心的忽略掉，因此我们得到了子问题EditDistance("hor","o")，由于执行了一次新增操作，因此：

EditDistance("hor","ro")=EditDistance("hor","o")+1

2，将word1的第一个字符删掉(Delete)，此时word1变为“or”，我们得到了一个新的子问题EditDistance("or","ro")，由于执行了一次删除操作，因此：

EditDistance("hor","ro")=EditDistance("or","ro")+1

3，将word1的第一个字符替换(Replace )为r，此时word1变为了“ror”，由于word1的第一个字符等于word2的第一个字符，因此可以放心的忽略掉，我们得到了一个新的子问题EditDistance("or","o")，由于执行了一次删除操作，因此：

EditDistance("hor","ro")=EditDistance("or","o")+1

根据题目要求，我们需要得到最小的编辑距离，因此：

EditDistance("hor","ro")=min(EditDistance("hor","o"),
EditDistance("or","ro"),
EditDistance("or","o"))+1

即：

可以看到，如果word1与word2的第一个字符如果不相等的话那么我们会得到三个子问题，取这三个子问题的最小值然后加1就是原始问题的解。

现在我们找到了子问题与原始问题之间的依赖关系。

实际上，根据上述讨论我们还可以进一步扩展从而得到完整的状态空间树。

从这棵树中可以看到最小的编辑距离是2。

现在你应该清楚的知道该怎样我们是怎样一步步将问题不断的分解为更小的子问题，然后利用子问题的解来得到原始问题的解了。

自顶向下递归代码

上图中每个方框都是一个子问题，决定一个子问题的因素在于word1与word2当前处理到了哪个位置，假设对word1处理到了第i个位置，对word2处理到了第j个位置，因此我们可以对问题进行定义：

intEditDistance(inti,intj);

该函数表示从i到word1的末尾形成的字符串与从j从word2的末尾形成的字符串的编辑距离。

因此如果调用该函数时我们应该这样使用：

EditDistance(0,0);

有了该定义与上述分析，你可以轻而易举的写出这样的递归代码：

stringword1;
stringword2;

intEditDistance(inti,intj){
if(i==word1.length()&&j==word2.length())return0;
if(i==word1.length())returnword2.length()-j;
if(j==word2.length())returnword1.length()-i;

if(word1[i]==word2[j])returnEditDistance(i+1,j+1);
else{
returnmin(EditDistance(i+1,j+1),min(
EditDistance(i,j+1),
EditDistance(i+1,j)))+1;
}
}

我们将word1与word2声明为全局变量，这样你可以清楚的看到决定EditDistance函数值的因素只有这两个参数i和j，i的取值为[0, word1.length()]，j的取值为[0, word2.length()]，也就是说子问题的个数只有(word1.length() + 1) * (word2.length() + 1) 个，上述递归代码存在大量重复计算问题，因此可以通过增加cache进行优化，这个改动就留给大家啦。

接下来我们着手将自顶向下的递归代码改为自底向上的动态规划代码。

自底向上动态规划代码

由于子问题的个数只有(word1.length() + 1) * (word2.length() + 1) 个，因此可以定义一个相同大小的二维数组dp:

vector>dp(word1.length()+1,vector(word2.length()+1,0));

接下来我们要求解最小子问题，最小子问题就是上述递归代码的递归出口：

if(i==word1.length()&&j==word2.length())return0;

该最小子问题的解包含在了dp数组的初始化中。

接下来的子问题是另外两个递归出口：

if(i==word1.length())returnword2.length()-j;
if(j==word2.length())returnword1.length()-i;

我们可以简单的构造出两种情况下的所有i和j来初始化数组dp，即：

for(intj=word2.length()-1;j>=0;j--)
dp[word1.length()][j]=word2.length()-j;
for(inti=word1.length()-1;i>=0;i--)
dp[i][word2.length()]=word1.length()-i;

最后我们利用两个for循环来构造出所有的i和j，从而将递归函数的最后一部分：

if(word1[i]==word2[j])returnEditDistance(i+1,j+1);
else{
returnmin(EditDistance(i+1,j+1),min(
EditDistance(i,j+1),
EditDistance(i+1,j)))+1;
}

放置在for循环中，并将对递归函数的调用替换为对数组dp的读写：

for(inti=word1.length()-1;i>=0;i--){
for(intj=word2.length()-1;j>=0;j--){
if(word1[i]==word2[j])
dp[i][j]=dp[i+1][j+1];
else
dp[i][j]=min(dp[i+1][j+1],min(dp[i][j+1],dp[i+1][j]))+1;
}
}

最终，完整的动态规划代码为：

intminDistance(stringword1,stringword2){
vector>dp(word1.length()+1,vector(word2.length()+1,0));
for(intj=word2.length()-1;j>=0;j--)
dp[word1.length()][j]=word2.length()-j;
for(inti=word1.length()-1;i>=0;i--)
dp[i][word2.length()]=word1.length()-i;
for(inti=word1.length()-1;i>=0;i--){
for(intj=word2.length()-1;j>=0;j--){
if(word1[i]==word2[j])
dp[i][j]=dp[i+1][j+1];
else
dp[i][j]=min(dp[i+1][j+1],min(dp[i][j+1],dp[i+1][j]))+1;
}
}

returndp[0][0];
}

审核编辑：刘清

声明：本文内容及配图由入驻作者撰写或者入驻合作网站授权转载。文章观点仅代表作者本人，不代表德赢Vwin官网网立场。文章及其配图仅供工程师学习之用，如有内容侵权或者其他违规问题，请联系本站处理。举报投诉

状态机

状态机

+关注

关注
2

文章
492

浏览量
27528

原文标题：彻底理解动态规划：编辑距离

文章出处：【微信号：TheAlgorithm，微信公众号：算法与数据结构】欢迎添加关注！文章转载请注明出处。

字节发布SeedEdit图像编辑模型

近日，字节跳动公司在其豆包大模型团队的官方网站上，正式公布了其最新的通用图像编辑模型——SeedEdit。这款创新性的图像编辑模型，为用户提供了前所未有的便捷图像编辑体验。据官方介绍

发表于 11-12 10:43 •244次阅读

OrCAD Capture 17.2 点击edit simulation profile没有反应

请问OrCAD capture 17.2点击edit simulation profile后没有反应应该怎么解决呢，可以正常绘制原理图，也可以跑仿真，但是没有simulation setting窗口弹出，无法修改仿真设置，求助各位！

发表于 09-19 22:28

vim编辑器如何使用

Vim编辑器是一个功能强大的文本编辑器，它基于Vi进行改进，并增加了许多新特性。Vim编辑器的使用主要涉及其不同的工作模式及相应操作。以下是Vim编辑器的基本使用方法：一、Vim

发表于 08-30 14:58 •427次阅读

如何理解PCB设计的爬电距离?

一站式PCBA智造厂家今天为大家讲讲PCB设计爬电距离要求与走线规则有哪些?PCB设计爬电距离要求与走线规则。在PCB设计中，爬电距离和走线规则是关键的考虑因素，尤其是在高压电路和高频电路的设计中

发表于 08-15 09:23 •1043次阅读

爬电距离是根据什么确定的

爬电距离（Creepage Distance）是指在电气设备中，两个导体之间沿绝缘材料表面的距离。它是一个重要的电气参数，用于评估电气设备在正常工作和故障条件下的绝缘性能。爬电距离的确

发表于 07-12 15:39 •907次阅读

爬电距离与电压的对应关系

爬电距离（Creepage Distance）是电气设备中的一个重要概念，它指的是在绝缘材料表面，沿着绝缘体表面或边缘，从带电部分到接地部分或不同电位部分之间的最短距离。爬电距离的大小

发表于 07-12 15:35 •2750次阅读

微软AI新成果：将不可编辑PDF转化为可编辑文档

市面现有相关软件虽能将PDF转为可编辑版，但易丧失原始布局。微软研究论文名为《从不可编辑文档生成可编辑文档的方法和系统》，其独特之处在于运用AI技术保持了字体、色彩、布局及图像格式等视觉元素的完整性。

发表于 05-30 10:11 •673次阅读

HarmonyOS开发案例：【图片编辑】

基于ArkTS的声明式开发范式的样例，主要介绍了图片编辑实现过程。

发表于 04-23 20:54 •386次阅读

HarmonyOS开发案例：【图片<b class='flag-5'>编辑</b>】

UCGUI edit输入框内字符串如何单独用光标选中某字符进行修改？

如题： UCGUI edit输入框内字符串如何单独用光标选中某字符进行修改？使用场景：对RTC芯片进行校时。GUI绘画虚拟键盘：edit输入框、虚拟按键；用于实现年月子时分秒时间的输入。现在

发表于 04-23 06:14

tftlcd画线程序里面xerr>distance和yerr>distance两个条件能成立吗？

实验中这个程序是没问题的，就是在个人读程序中，无法理解if(xerr>distance) 和if(yerr>distance) 两个条件，个人认为distance选取

发表于 04-22 07:35

使用EDIT_SetDecMode()函数设置十进制编辑后变成了一个黑块的原因？

使用了EDIT_SetDecMode()函数设置十进制编辑后，就变成这样；但是在电脑上仿真界面的时候，数字和背景是会自动反色的，但下载到单片机上就是一个黑色块。请问会是什么原因？

发表于 04-12 06:12

arcgis图层字段怎么批量输入属性

对于ArcGIS图层字段的批量输入属性，可以通过以下步骤完成：打开ArcMap软件，并加载需要编辑属性的图层。在ArcMap的主菜单中，选择“编辑（Edit）”选项，然后选择“开始编辑

发表于 02-25 14:15 •4888次阅读

CCS edit Flags有bug

今天发现编辑完Build->Edit Flags里面的内容后会被自动更新出错，请问这个问题如何解决呢？我编辑如此： -v28 -ml -mt --cla_support=cla1

发表于 02-24 17:50

变频器在长距离供电时末端电压会升高还是降低？

理解，但是有一点，如果在电能传输距离很长时，会导致末端电压的变化，我搜了百度上面的一些回答，有的说过长的传输距离会导致末端电压升高，但是这与我平常的认知理解不一样，

发表于 01-11 18:50

解读光模块波长与传输距离的关系波长是影响光模块传输距离的因素吗

领域，理解和优化光模块的波长选择对于实现高速、长距离光纤通信至关重要。首先，我们需要了解光模块和波长的基本概念。光模块是将电信号转换为光信号，并在光纤中传输的设备。波长指的是光信号的频率或色彩。对于常用的通

发表于 12-27 11:28 •1350次阅读

搜索历史

彻底理解编辑距离问题edit distance

评论