最小编辑代价

[编程题]最小编辑代价

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

Python

离疏

# -*- coding:utf-8 -*-
#分析：
    #dp[i][j]代表用 str1[0~i-1]编辑乘str2[0~j-1]的最小代价
#分析简单情况：
    #dp[0][j]:即把一个空串编辑乘str2[0~j-1]的代价则即将j个字符全部插入即
        #dp[0][j] = j*c0;
    #dp[i][0]:即把str1[0~i-1]编辑乘空串的代价,即将i个字符全部删除即
        #dp[i][0] = i*c1
    #dp[i][j]:分四种情况：
    #1) 先把str1[0~i-1]编辑成str1[0~i-2],在把str1[0~i-2]编辑成str2[0~j-1]
        #dp[i][j] = dp[i-1][j] + c1;
    #2) 先把str1[0~i-1]编辑成str2[0~j-2],在把str2[0~j-2]编辑成str2[0~j-1]
        #dp[i][j] = dp[i][j-1] + c0;
    #3) 如果str1[i-1] != str2[j-1],则可以先将str1[0~i-2]编辑成str2[0~j-2],然后进行替换
        #dp[i][j] = dp[i-1][j-1] + c2;
    #4) 如果str1[i-1] == str2[j-1],则直接将str1[0~i-2]编辑成str2[0~j-2]
        #dp[i][j] = dp[i-1][j-1]
    #从以上情况中选择代价最小的一种情况
    
class MinCost:
    def findMinCost(self, A, n, B, m, c0, c1, c2):
        dp=[[0 for i in range(m+1)]for i in range(n+1)]
        for i in range(n+1):#初始化dp[0][j]
            dp[i][0]=i*c1
        for j in range(m+1):#初始化dp[i][0]
            dp[0][j]=j*c0
        for i in range(1,n+1):#其他情况
            for j in range(1,m+1):
                dp[i][j]=min(dp[i-1][j]+c1,dp[i][j-1]+c0)
                if A[i-1]==B[j-1]:
                    dp[i][j]=min(dp[i-1][j-1],dp[i][j])
                else:
                    dp[i][j]=min(dp[i-1][j-1]+c2,dp[i][j])
        return dp[n][m]

发表于 2018-09-25 11:15:36 回复(0)