最小编辑代价

[编程题]最小编辑代价

对于两个字符串A和B，我们需要进行插入、删除和修改操作将A串变为B串，定义c0，c1，c2分别为三种操作的代价，请设计一个高效算法，求出将A串变为B串所需要的最少代价。

给定两个字符串A和B，及它们的长度和三种操作代价，请返回将A串变为B串所需要的最小代价。保证两串长度均小于等于300，且三种代价值均小于等于100。

测试样例：

"abc",3,"adc",3,5,3,100

返回：8

算法知识视频讲解

重生之我要当分子

发表于 2025-01-01 00:23:41

解题思路这是一个编辑距离问题的变种。关键点：动态规划定义：表示将的前个字符转换为的前个字符的最小代价：插入代价：删除代价：修改代价状态转移：当时：否则取以下三种操作的最小值：插入：删除：修改：边界条件：（全部删除）（全部展开全文

问题信息

动态规划

来自：面试常考算法题(九)-...

难度：

36条回答 96收藏 16557浏览

查看代码

最小编辑代价

扫一扫，把题目装进口袋