# 最小编辑代价

[编程题]最小编辑代价
• 热度指数：4607 时间限制：C/C++ 3秒，其他语言6秒 空间限制：C/C++ 32M，其他语言64M
• 算法知识视频讲解

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];
}

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];
}
}

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];
}
};

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];

}

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];
}
}

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];
}
};

package dp;
/**

*/
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];
}

}

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];
}
};

//动态规划， 只用了一维数组，节省内存
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];
}
};

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];
}
};

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];
}
}

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;
}
}

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];
}
};

/*
分析：
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];
}

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];
}
};

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()];
}
};

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];
}
};

# -*- 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]

/*
* 参考上面大神的解题思路
* */
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];
}
}

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];
}
}

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];
}
};

36条回答 15719浏览

## 通过挑战的用户

• 2022-12-13 21:46:03
• 2022-08-27 18:38:57
• 2022-08-22 16:58:11
• 2022-08-20 21:05:04
• 2022-07-28 17:08:39

## 相关试题

• 扫描二维码，关注牛客网

• 下载牛客APP，随时随地刷题