首页 > 试题广场 >

最小编辑代价

[编程题]最小编辑代价
  • 热度指数：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)
Alex-大伟头像 Alex-大伟 
package alex.suda.dp;

import java.util.Scanner;

public class test4 {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner scanner = new Scanner(System.in);
		while (scanner.hasNext()) {
			int n = scanner.nextInt();
			String A = scanner.next();
			int m = scanner.nextInt();
			String B = scanner.next();
			int c0 = scanner.nextInt();
			int c1 = scanner.nextInt();
			int c2 = scanner.nextInt();
			System.out.print(findMinCost(A, n, B, m, c0, c1, c2));
		}
	}

	public static int findMinCost(String A, int n, String B, int m, int c0, int c1, int c2) {
		// 设d[i][j]为将字符串A的1~i位和B的1~j位变为相同时的操作代价
		// 注意题目是：A串变为B串 而不是将两个字符串变为相等
		// d[i][j] = d[i-1][j-1]， 如果A[i] = A[j]
		// 否则可以： 1. A的末端插入B的最后一位
		// 2.删除A的末端
		// 3.修改A的末端为B的末端 
		int[][] d = new int[n + 1][m + 1];
		// 初始化
		for (int i = 0; i <= n; i++) {
			d[i][0] = i * c1;
		}
		for (int j = 0; j <= m; j++) {
			d[0][j] = j * c0;
		}
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= m; j++) {
				if (A.charAt(i - 1) == B.charAt(j - 1)) {
					d[i][j] = d[i - 1][j - 1];
				} else {
					int cost1 = d[i][j - 1] + c0;// 插入时的代价
					int cost2 = d[i - 1][j] + c1;// 删除的代价
					int cost3 = d[i - 1][j - 1] + c2;//修改的代价
					d[i][j] = Math.min(cost1, Math.min(cost2, cost3));
				}
			}
		}
		return d[n][m];
	}
}


发表于 2016-10-05 22:12:48 回复(1)
是尘埃也是宇宙头像 是尘埃也是宇宙 
int dp[505][505];

class MinCost {
public:
    int findMinCost(string A, int n, string B, int m, int c0, int c1, int c2) {
        // write code here
        memset(dp, 0x3f, sizeof(dp));
        dp[0][0] = 0;

        c2 = min(c2, c0+c1);			//修改 = 先删除后插入
        for(int i=0; i<=n; i++)
            for(int j=0; j<=m; j++){
                int edit = A[i-1]!=B[j-1]? c2: 0;

                if(j)	dp[i][j] = min(dp[i][j], dp[i][j-1] + c0);
                if(i)	dp[i][j] = min(dp[i][j], dp[i-1][j] + c1);	 
                if(i&&j)dp[i][j] = min(dp[i][j], dp[i-1][j-1] + edit);	
            }

        return dp[n][m];
    }
};
发表于 2015-09-12 14:00:50 回复(2)
呦呵呵头像 呦呵呵
动态规划
public static int findMinCost(String A, int n, String B, int m, int c0, int c1, int c2) {
// write code here
//开辟大小为（n+1）*（m+1）的二维数组dp(考虑空串)
//dp[i][j]表示字符串str1[0..i-1]编辑成str2[0..j-1]的最小代价
int[][] dp = new int[n+1][m+1];
//dp[0][0]表示字符串str1空串替换成字符串sttr2空串的代价 0
dp[0][0] = 0;
//第一行dp[0][0..i]表示字符串str1空串替换成字符串str2的代价 即只能插入 插入代价为 i*c0
for(int i=0;i<=m;i++){
dp[0][i]= i*c0;
}
//第一列dp[0...j][0]表示字符串str1编辑成str2空串的代价 即只能删除 删除代价为 j*c1
for(int j=0;j<=n;j++){
dp[j][0] = j*c1;
}
//其他位置dp[i][j]表示字符串str1[0...i-1]编辑成str2[0...j-1]的代价 有四种情况(注意数组下标)
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
int maxValue1 = Integer.MAX_VALUE;
int maxValue2 = Integer.MAX_VALUE;
if(A.charAt(i-1) != B.charAt(j-1)){
//(1)dp[i][j]：str1[i-1] != str2[j-1]时 ,
//str1[0..i-2]先编辑成str2[0...j-2] 然后用str2[j-1]替换str1[i-1]
maxValue1 = dp[i-1][j-1]+c2;
}
if(A.charAt(i-1) == B.charAt(j-1)){
//(2)dp[i][j] :str1.charAt(i-1) == str2.charAt(j-1)时
//str1[i-2]编辑成str2[j-2]即可 即dp[i][j] = dp[i-1][j-1];
//dp[i][j]表示字符串str1[0...i-1]编辑成str2[0...j-1]的代价
maxValue2 = dp[i-1][j-1];
}
//(3)dp[i][j] str1[0...i-1]先编辑成str1[0..i-2]  代价1：c1(删除)
//然后由str1[0..i-2]编辑成str2[0...j-1] 代价2：dp[i-1][j]的代价
//总代价dp[i][j]=dp[i-1][j]+c1
//(4)dp[i][j] str1[0...i-1]先编辑成str2[0..j-2] 代价1：dp[i][j-1]
//然后插入str2[j-1] 代价2：c0
//总代价dp[i][j]= dp[i][j-1]+c0
//以上四种代价选最小
int minValue1= (dp[i-1][j] + c1) < (dp[i][j-1] + c0) ? (dp[i-1][j] + c1) : (dp[i][j-1] + c0);
int minValue2 = maxValue1 < maxValue2 ? maxValue1 : maxValue2;
dp[i][j] = minValue1 < minValue2 ? minValue1 : minValue2;
}
}
//最后 二维数组最右下角dp[n][m]即为字符串str1[0..n-1]替换成str2[0..m-1]的最小代价
return dp[n][m];

}
编辑于 2019-08-18 21:35:00 回复(0)
ZhanHeng头像 ZhanHeng 
import java.util.*;

public class MinCost {    public int findMinCost(String str1, int n, String str2, int m, int ic, int dc, int uc) {  int [][]dp=new int [n+1][m+1];
       //第一列表示str1到空串需要的代价所以是删除代价的倍数，
       //第一行表示空串到str2需要的代价所以是添加代价的倍数
       for(int i=1; i<=n ;i++)
           dp[i][0]=i*dc; 
       for(int i=1; i<=m ;i++)
           dp[0][i]=i*ic;
        //dp[i][j]表示str1[0..i-1]变到str2[0..j-1]需要的最小代价
       for(int i=1 ;i<=n ;i++){
           for(int j=1 ;j<=m ;j++){
               //字符相等代价不变，不等就加上修改代价
               if(str1.charAt(i-1)==str2.charAt(j-1)){
                   dp[i][j]=dp[i-1][j-1];
               }else{
                   dp[i][j]=dp[i-1][j-1]+uc;
               }
               //str1前面[0..i-2]的部分变成了str2[0..j-1],加一个删除代价
               //str1[0..i-1]变成了str2前面的[0..j-2]部分,加一个添加代价
               //然后取三个代价的最小值更新到dp[i][j]
              dp[i][j]= Math.min(dp[i][j],dp[i][j-1]+ic);
              dp[i][j]= Math.min(dp[i][j],dp[i-1][j]+dc);
           }
       }
        return dp[n][m];
    }
}

编辑于 2016-04-22 21:45:45 回复(6)
C/C++
nbgao头像 nbgao 
class MinCost {
public:
    int findMinCost(string A, int n, string B, int m, int c0, int c1, int c2) {
        int dp[n+1][m+1];
        dp[0][0] = 0;
        for(int i=1;i<=n;i++)
            dp[i][0] = dp[i-1][0] + c1;
        for(int j=1;j<=m;j++)
            dp[0][j] = dp[0][j-1] + c0;
        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] = min(dp[i-1][j-1]+c2, min(dp[i-1][j]+c1, dp[i][j-1]+c0));             }         return dp[n][m];
    }
};

发表于 2017-10-30 00:56:49 回复(0)
M00N头像 M00N 
package dp;
/**
最小编辑代价

题目描述:
对于两个字符串A和B，我们需要进行插入、删除和修改操作将A串变为B串，
定义c0，c1，c2分别为三种操作的代价，请设计一个高效算法，求出将A串变为B串所需要的最少代价。
给定两个字符串A和B，及它们的长度和三种操作代价，请返回将A串变为B串所需要的最小代价。
保证两串长度均小于等于300，且三种代价值均小于等于100。
测试样例：
"abc",3,"adc",3,5,3,100
返回：8

思路：动态规划
 */
public class MinEditCost {
	
    public int findMinCost(String str1, int m, String str2, int n, int ic, int dc, int rc) {
    	
    	char[] s1 = str1.toCharArray();
    	char[] s2 = str2.toCharArray();
    	int[][] dp = new int[m+1][n+1];
    	//第一行
    	for (int i = 0; i <= n; i++) {
    		dp[0][i] = i*ic;
    	}
    	//第一列
    	for (int i = 0; i <= m; i++) {
    		dp[i][0] = i*dc;
    	}
    	
    	for (int i = 1; i <= m; i++) {
    		for(int j = 1; j <= n; j++) {
    			if (s1[i-1] == s2[j-1]) {
    				dp[i][j] = dp[i-1][j-1];
    			} else {
    				dp[i][j] = dp[i-1][j-1] + rc;
    			}
    			dp[i][j] = Math.min(dp[i][j], dp[i-1][j]+dc);
    			dp[i][j] = Math.min(dp[i][j], dp[i][j-1]+ic);
    		}
    	}
    	return dp[m][n];
    }
    
}


发表于 2017-04-03 19:14:27 回复(0)
萌头像 萌 
class MinCost {
public:
	int findMinCost(string A, int n, string B, int m, int cr, int sc, int th) {
		// write code here
		vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
		dp[0][0] = 0;
		for (size_t i = 1; i < m+1; i++)//第一行
		{
			dp[0][i] = i*cr;
		}
		for (size_t i = 1; i < n + 1; i++)//第一行
		{
			dp[i][0] = i*sc;
		}
		for (size_t i = 1; i < n+1; i++)
		{
			for (size_t j = 1; j < m+1; j++)
			{
				if (A[i-1]==B[j-1])
				{
					dp[i][j] = dp[i - 1][j - 1];
				}
				else
				{
					dp[i][j] = min(dp[i][j - 1] + cr, min(dp[i - 1][j] + sc, dp[i - 1][j - 1] + th));
				}
			}
		}
		return dp[n][m];
	}
};

发表于 2016-08-30 22:12:36 回复(0)
C/C++
lowbee头像 lowbee 
//动态规划， 只用了一维数组，节省内存
class MinCost {
public:
    int findMinCost(string A, int n, string B, int m, int ic, int dc, int sc) {
        // write code here
         
         
        
        if(m==0) return dc*n;
        
        if(n==0) return ic*m;
        
        vector<int> dp(m+1,0); // dp[j] = dp[i][j]
        
        for(int j=1;j<=m;j++) // init dp[0][0]
            dp[j] = dp[j-1]+ic;   // dp
        
        
        int corner=0,minCost; // corner = dp[i-1][j-1]
       
        for(int i=1;i<=n;i++){
            dp[0] = dp[0]+dc;  // dp[i][0] = dp[i-1][0]
            for(int j=1;j<=m;j++){
            	 
            	if(A[i-1]==B[j-1])
                	minCost = corner;
            	else
                    minCost = corner+sc;
                minCost = min(minCost,dp[j-1]+ic);// inserte B[i]    dp[j-1] = dp[i][j-1]
                minCost = min(minCost,dp[j]+dc) ;  //delete A[i]  dp[j]=dp[i-1][j]
           
            
                corner = dp[j]; // update dp[i-1][j-1] -> dp[i-1][j]
            
            
                 
                dp[j] = minCost; //dp[j] = dp[i][j]
             }
            corner = dp[0]; // update corner -> dp[i][0] 
        }
        return dp[m];
    }
};

发表于 2016-08-30 16:40:08 回复(0)
OnePiece~~头像 OnePiece~~ 
class MinCost {
public:
    int findMinCost(string A, int n, string B, int m, int c0, int c1, int c2) {
        // write code here
        //动态规划，利用dp[][]数组。
        vector<vector<int> >dp(n+1,vector<int>(m+1,0));
        for(int i=0;i<=m;i++)
            dp[0][i]=i*c0;
        for(int j=0;j<=n;j++)
            dp[j][0]=j*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]=dp[i-1][j-1]+c2;
                }
                dp[i][j]=dp[i][j]>dp[i-1][j]+c1? dp[i-1][j]+c1:dp[i][j];
                dp[i][j]=dp[i][j]>dp[i][j-1]+c0? dp[i][j-1]+c0:dp[i][j];
            }
        }
        return dp[n][m];
    }
};

发表于 2016-08-14 16:17:58 回复(0)
从前从前有个人爱你很久头像 从前从前有个人爱你很久 
import java.util.*;
//参考:http://blog.csdn.net/u014041033/article/details/51142331
public class MinCost {
	//c0:插入;c1:删除;c2:修改
    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[i][j]代表从A[0..i],变为B[0..j]的最小代价! 
    	//为了方便计算,第一行第一列添加空字符,A[0]＝“” B[0]＝“”  dp[n+1][m+1]
    	//外边界初始化
    	for(int i=1; i<=n; i++){				//i从1-n,防止i-1越界
    		dp[i][0] = dp[i-1][0] + c1;
    	}
    	for(int i=1; i<=m; i++){
    		dp[0][i] = dp[0][i-1] + c0;
    	}
    	for(int i=1; i<=n; i++){
    		for(int j=1; j<=m; 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-1][j]+c1, dp[i][j-1]+c0));
    			}
    		}
    	}
    	return dp[n][m];
    }
}

发表于 2016-05-13 16:49:13 回复(0)
FuestcK头像 FuestcK 
import java.util.*;

public class MinCost {
    public int findMinCost(String A, int n, String B, int m, int c0, int c1, int c2) {
        int len=n>m?n:m;
        /*d[i][j]表示字符串A的前i个字符构成的子串
        和字符串B的前j个字符构成的子串的最短编辑距离
        则d[n][m]为所求最终结果*/
        int d[][]=new int[len+1][len+1];
        c2=Math.min(c0+c1,c2);
        /*边界条件*/
        for(int i=0;i<=len;i++){
            d[i][0]=i*c1;
        }
        for(int j=0;j<=len;j++){
            d[0][j]=j*c0;
        }
        /*转移方程*/
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                if(A.charAt(i-1)==B.charAt(j-1)){
                    d[i][j]=d[i-1][j-1];
                }else{
                    d[i][j]=min(d[i-1][j]+c1,/*删除*/
                                d[i][j-1]+c0,/*插入*/
                                d[i-1][j-1]+c2);/*修改*/
                }
            }
        }
        return d[n][m];
    }
     public int min(int a,int b,int c){
        int t=a>b?b:a;
        return t>c?c:t;
    }
}

发表于 2016-04-04 21:44:01 回复(0)
还有多远头像 还有多远
注意，我们是将A编辑成B，这个过程中只能编辑A 
class MinCost {
public:
    int findMinCost(string A, int n, string B, int m, int c0, int c1, int c2) {
        //f[i][j] represent the cost to edit A[i, n) to B[j, m)
        vector<vector<int>> f(n+1, vector<int>(m+1));
        //try to let A[n, n) to match B[m, m), just null to null
        f[n][m] = 0;
        for(int i = 0; i < n; ++i){
            //try to let A[i, n) to match B[m, m), have to delete all
            f[i][m] = (n-i) * c1;
        }
        for(int j = 0; j < m; ++j){
            //try to let A[n, n) to match B[j, m), have to insert all
            f[n][j] = (m-j) * c0;
        }
        for(int i = n-1; i > -1; --i){
            for(int j = m-1; j > -1; --j){
                if(A[i] == B[j]) f[i][j] = f[i+1][j+1];
                else{
                    //try to let A[i+1,n) match B[j,m), operation is delete A[i]
                    f[i][j] = f[i+1][j] + c1;
                    //try to let A[i,n) match B[j+1,m), operation is insert B[j]
                    f[i][j] = min(f[i][j], f[i][j+1] + c0);
                    //try to make A[i] equal to B[j]
                    if(c0 + c1 < c2){
                        //better way is delete then insert
                        f[i][j] = min(f[i][j], f[i+1][j+1] + c0 + c1);
                    }
                    else{
                        //better way is replace A[i] by B[j]
                        f[i][j] = min(f[i][j], f[i+1][j+1] + c2);
                    }
                }
            }
        }
        return f[0][0];
    }
};

发表于 2015-08-06 00:45:18 回复(0)
牛客3897179号头像 牛客3897179号 
/*
    分析：
	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]
	从以上情况中选择代价最小的一种情况
*/
    int findMinCost(string A, int n, string B, int m, int c0, int c1, int c2) 
    {
        vector<vector<int>> dp(n + 1, vector<int>(m + 1));
        //初始化dp[0][j]
        for (int j = 0; j <= m; j++)
        {
            dp[0][j] = j*c0;
        }
        //初始化dp[i][0]
        for (int i = 0;i <= n; i++)
        {
            dp[i][0] = i*c1;
        }
        //其他情况
        for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j <= m; j++)
            {
                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];
    }

发表于 2017-09-02 14:15:29 回复(0)
MG_Reading头像 MG_Reading 
class MinCost {
public:
    int findMinCost(string A, int n, string B, int m, int c0, int c1, int c2) {
        // write code here
        vector<vector<int> >dp(n+2, vector<int>(m+2));
        for(int i=0;i<=n; i++){
            for(int j=0; j<=m; j++){
                if(j==0) dp[i][j] = i*c1;//A->0 delete
                else if(i==0) dp[i][j] = j*c0;
                else{
                    int cost = A[i-1]==B[j-1]?0:1;//注意一下字符串下标是从0开始的
                    int a = dp[i-1][j] + c1;// i-1->j delete i
                    int b = dp[i][j-1] + c0;// i->j-1 insert j
                    int c = dp[i-1][j-1] + cost*c2;
                    dp[i][j] = min(a, min(b,c));
                }
            }
        }
       return dp[n][m];
    }
};

发表于 2020-07-25 16:59:23 回复(0)
momococo头像 momococo 

	classMinCost {





	public:





	intfindMinCost(string A, intn, string B, intm, intc0, intc1, intc2) {





	





	    vector<int>dp(B.size() + 1, 0);





	    for(intj = 0; j <= B.size(); ++j){





	        dp[j] = c0*j;





	    }





	    for(inti = 1; i <= A.size(); ++i)





	    { //左上角的值 





	        int pre = dp[0];





	        dp[0] = c1*i;





	        for(intj = 1; j <= B.size(); ++j)





	        { //正上方的值 





	            int tmp = dp[j];





	            if(A[i - 1] == B[j - 1])





	                dp[j] = pre;





	            else dp[j] = pre + c2;





	            dp[j] = min(dp[j], dp[j - 1] + c0);





	            dp[j] = min(dp[j], tmp + c1);





	            pre = tmp;





	        }





	    }





	return  dp[B.size()];





	}





	};

编辑于 2019-04-23 17:33:59 回复(0)
C/C++
~似曾相识燕归来头像 ~似曾相识燕归来 
class MinCost {
public:
    int findMinCost(string A, int n, string B, int m, int c0, int c1, int c2) {
        int iValue = c0;
        int dValue = c1;
        int mValue = c2;

        vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
        for (int i = 1; i <= n; i++) {
            dp[i][0] = dValue * i;
        }
        for (int i = 1; i <= m; i++) {
            dp[0][i] = iValue * i;
        }

        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 {
                    // modify cost
                    int modifyCost = dp[i - 1][j - 1] + mValue;
                    // insert cost
                    int insertCost = dp[i][j - 1] + iValue;
                    // delete cost
                    int deleteCost = dp[i - 1][j] + dValue;

                    dp[i][j] = min(modifyCost, min(insertCost, deleteCost));
                }
            }
        }

        return dp[n][m];
    }
};
发表于 2019-04-04 16:49:31 回复(0)
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)
逗比请来的猴子头像 逗比请来的猴子 
/*
 * 参考上面大神的解题思路
 * */
public class MinCost {
    //    dp[i][j] 表示将长为i的字符串n转换成长为j的字符串m需要的代价
    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];
        for (int i = 1; i <= n; i++) {
//            不断删除
            dp[i][0] = dp[i - 1][0] + c1;
        }

        for (int i = 1; i <= m; i++) {
//            不断插入
            dp[0][i] = dp[0][i - 1] + c0;
        }

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (A.charAt(i - 1) == B.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];
                    /*
                     * 调整的时候有三种情况，
                     * 修改：dp[i-1][j-1]基础上修改
                     * 插入：dp[i][j-1]基础上往m中插入一个字符
                     * 删除：dp[i-1][j]，i-1长度的n已经转变成j长度的m，那么只需要删除一个字符就可以
                     * */
                } else {
                    dp[i][j] = Math.min(dp[i - 1][j] + c0, Math.min(dp[i][j - 1] + c1, dp[i - 1][j - 1] + c2));
                }
            }
        }
        return dp[n][m];
    }
}
发表于 2018-03-25 16:56:39 回复(0)
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)
MonchiDluffy头像 MonchiDluffy
classMinCost {
public:
    intfindMinCost(string A, intn, string B, intm, intc0, intc1, intc2)
    {
        intdp[n + 1][m + 1];
        dp[0][0] = 0;
        for(inti = 1; i <= n; i++) dp[i][0] = i * c1; // 是删除操作, 随着增加而增加
        for(intj = 1; j <= m; j++) dp[0][j] = j * c0; // 增加操作，随着增加而增加
        for(inti = 0; i < n; i++)
        {
            for(intj = 0; j < m; j++)
            {
                inttemp1 = 0;
                if(A[i] == B[j])
                {
                    temp1 = dp[i][j]; // 某位置上的相等就等于左上角的值
                }
                else
                {
                    temp1 = dp[i][j] + c2; // 不等就等于左上角的值加上修改的操作
                }
                inttemp2 = min(dp[i][j + 1] + c1, dp[i + 1][j] + c0); // 还有添加或者删除的操作的情况
                dp[i+1][j+1] = min(temp1, temp2); // 最后取三种情况的最小值
            }
        }
        returndp[n][m];
    }
};
发表于 2017-08-28 15:51:52 回复(0)
提交观点

问题信息

动态规划
来自：面试常考算法题(九)-...
难度：
36条回答 16154浏览

热门推荐

通过挑战的用户

查看代码

相关试题

最小编辑代价

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号