最小编辑代价

[编程题]最小编辑代价

热度指数：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)

Java

安徒生的谎言

动态规划问题只不过将代价都为1变成了指定的，注意初始化以及状态方程即可：
import java.util.*;

public class MinCost {
    public static int findMinCost(String A, int n, String B, int m, int c0, int c1, int c2) {
        // write code here
        int[][] dis=new int[n+1][m+1];
        for(int i=0;i<=n;i++) {
            dis[i][0]=i*c1;
        }
        for(int j=0;j<=m;j++) {
            dis[0][j]=j*c0;
        }
        for(int i=1;i<=n;i++) {
            for(int j=1;j<=m;j++) {
                dis[i][j]=Math.min(dis[i][j-1]+c0, Math.min(dis[i-1][j]+c1,dis[i-1][j-1]+(A.charAt(i-1)==B.charAt(j-1)?0:c2 )));
            }
        }
        return dis[n][m];
    }
}

发表于 2018-01-26 11:03:56 回复(0)

Java

詆調壹點

import java.util.*;
public class MinCost {
  public int findMinCost(String A, int n, String B, int m, int c0, int c1, int c2) {
		int[][] dp = new int[n + 1][m + 1];
		dp[0][0] = 0;
		for (int i = 1; i <= m; i ++ ) {
			dp[0][i] = c0 * i;
		}
		for (int i = 1; i <= n; i ++ ) {
			dp[i][0] = c1 * i;
		}
		for (int i = 1; i < dp.length; i ++ ) {
			for (int j = 1; j < dp[0].length; j ++ ) {
				if(A.charAt(i - 1) == B.charAt(j - 1)) dp[i][j] = dp[i - 1][j - 1];
				else dp[i][j] = Math.min(dp[i - 1][j - 1] + c2, Math.min(dp[i][j - 1] + c0, dp[i - 1][j] + c1));
			}
		}
		return dp[n][m];
	}
}

发表于 2016-10-09 21:49:10 回复(0)