使用动态规划解决编辑距离问题
发布时间
阅读量：
阅读量
编辑距离问题——动态规划
问题描述：
编辑距离的概念是指两个字串之间由一个转成另一个所需的最少编辑操作次数。
其中允许的操作有三种类型：将一个字符替换成另一个字符；插入一个新的字符；删除现有的一个字符。
例如：
将EXPONENTIAL转成POLYNOMIAL，最少需要6次编辑操作。如下图：
分析：
按照算法概论中的分析图所示：在对齐后的表格中右侧最后一列仅包含以下三种情形：
第一种情形下会产生生成费用一元的同时解决将x序列前i−一元素与y序列前f项更好地配准的问题这正是对应的子问题是E(i−一,f)。
第二种情形下同样会产生生成费用一元而剩余的部分则是解决将x序列前i项与y序列前j−一项更好配准的问题对应的子问题是E(i,j−一)。
第三种情形下则会根据两字符是否匹配来决定当前生成费用是零还是壹余下的部分则由解决将x序列前i−一项与y序列前j−一项更好配准的问题所决定。
还没有任何评论哟~