鸿 网 互 联 www.68idc.cn

当前位置 : 服务器租用 > 编程语言开发 > c++ > >

最小编辑代价

来源:互联网 作者:佚名 时间:2016-06-16 09:04
对于两个字符串A和B,我们需要进行插入、删除和修改操作将A串变为B串,定义c0,c1,c2分别为三种操作的代价,请设计一个高效算法,求出将A串变为B串所需要的最少代价。 给定两个字符串A和B,及它们的长度和三种操作代价,请返回将A串变为B串所需要的最小代价
对于两个字符串A和B,我们需要进行插入、删除和修改操作将A串变为B串,定义c0,c1,c2分别为三种操作的代价,请设计一个高效算法,求出将A串变为B串所需要的最少代价。

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

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

返回:8 <无>
/*************************************************************************************
/*
    当A=="" 或者B==""时,cost是删除或插入的代价
    当A!="" 且 B!= ""时
    A[i] == B[j] D[i][j] = D[i-1][j-1]
    A[i] != B[j] D[i][j] = MIN{D[i-1][j-1]+c2(修改一个值),D[i-1][j]+c1(删除一个值),D[i][j-1]+c0(插入一个值)}
*/
**************************************************************************************/
class MinCost {
public:
    int findMinCost(string A, int n, string B, int m, int c0, int c1, int c2) 
    {
        // write code here
        if(n==0 && m == 0)
            return 0;
        int dp[n+1][m+1];
        dp[0][0] = 0;
         
   
        for(int i = 1; i <= m; ++i)
            dp[0][i] = dp[0][i-1] + c0;
        
        for(int i = 1; i <= n; ++i)
            dp[i][0] = dp[i-1][0] + c1;
        
        for(int i = 1; i <= n; ++i)
            for(int j = 1; j <= m; ++j)
		{
            if(A[i-1] == B[j-1])
                dp[i][j] = dp[i-1][j-1];
            else
                dp[i][j] = t_min(dp[i-1][j-1]+c2,dp[i-1][j]+c1,dp[i][j-1]+c0);
        }
        return dp[n][m];
    }
private:
    int t_min(int a, int b, int c)
    {
        int m = (a < b) ? a : b;
        return (m < c) ? m : c;
    }
};
网友评论
<