最小编辑代价

[编程题]最小编辑代价

热度指数：3329 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定两个字符串str1和str2，再给定三个整数ic，dc和rc，分别代表插入、删除和替换一个字符的代价，请输出将str1编辑成str2的最小代价。

输入描述:

输出三行，第一行和第二行均为一行字符串，分别表示两个字符串str1，str2。。第三行为三个正整数，代表ic，dc和rc。（1<=ic<=10000、1<=dc<=10000、1<=rc<=10000）

输出描述:

输出一个整数，表示编辑的最小代价。

示例1

输入

abc
adc
5 3 2

输出

示例2

输入

abc
adc
5 3 100

输出

示例3

输入

abc
abc
5 3 2

输出

备注:

时间复杂度，空间复杂度。(n,m代表两个字符串长度)

算法知识视频讲解

星晨

发表于 2020-11-15 16:48:08

最小代价，毋庸置疑动态规划和之前的最小次数比，区别点在插入，删除，替换这几个代价是不同的，所以就需要区分出来那种可以实现当前的效果，然后找最小我们先不考虑状态压缩来进行分析 dp[i][j] 标示 str1[0,i] 变为 str2[0,j] 的最小代价则 dp[i][j] = dp[i- 展开全文