最小编辑代价

[编程题]最小编辑代价

热度指数：4626 时间限制：C/C++ 3秒，其他语言6秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

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

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

测试样例：

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

返回：8

算法知识视频讲解

查看答案及解析

推荐

在拧螺丝的起司很愉快

public static int findMinCost(String A, int n, String B, int m, int c0, int c1, int c2) {
        // write code here
		/*
			当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(插入一个值)}
		*/
        int[][] D = new int[n+1][m+1];
        for(int i = 1; i < n + 1;i ++){
            D[i][0] = D[i-1][0] + c1;
        }
        for(int j = 1; j < m + 1 ; j ++){
            D[0][j] = D[0][j-1] + c0;
        }
        for(int i = 1; i < n + 1; i ++){
            for(int j = 1; j < m + 1 ; j ++){
				if (A.charAt(i - 1) == B.charAt(j - 1))
                {
                    D[i][j] = D[i - 1][j - 1];
                }
                else
                {
                    D[i][j] = Math.min(D[i - 1][j - 1] + c2, Math.min(D[i][j - 1] + c0, D[i - 1][j] + c1));
                }
            }
        }
        return D[n][m];
	}

编辑于 2015-08-18 14:12:54 回复(3)