学习交流加

  • 个人qq：
    1126137994
  • 个人微信：
    liu1126137994
  • 学习交流资源分享qq群：
    962535112

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

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

测试样例：
“abc”,3,“adc”,3,5,3,100
返回：8

解题思路：
假设A的长度为n,B的长度为m，首先生成一个dp矩阵，dp[n+1]m+1,dp[i][j]代表将A[0(i-1)]变成B[0(j-1)]的最小代价。
1、先求第一行：
dp[0][j],将空串变成B[0…j-1],直接一个一个插入：

for(int j=0;j<m+1;j++)
        {
            dp[0][j]=j*ic;//ic代表插入的操作的代价
        }

2、再求第一列：
将A[0…i-1]变成空串,直接一个一个删除：

for(int i=0;i<n+1;i++)
        {
            dp[i][0]=i*dc;//dc代表删除的操作代价
        }

3、求其他行的值：
求其他行的值，可以大致分为以下四种情况：

一、
先把A[0(i-1)]编辑成A[0(i-2)],也就是删除字符A[i-1],再将A[0(i-2)]编辑成B[0(j-1)]，dp[i-1][j],所以：
dp[i][j]=dc+dp[i-1][j]

二、
先把A[0(i-1)]编辑成B[0(j-2)],即dp[i][j-1],再将B[0~(j-2)]插入B[j-1],所以：
dp[i][j]=ic+dp[i][j-1]

三、
如果A[i-1]!=B[j-1],那么先把A[0(i-2)]编辑成B[0(j-2)],然后把A[i-1]替换成B[j-1]即可！！！所以：
dp[i][j]=rc+dp[i-1][j-1];

四、
如果A[i-1]=B[j-1]，那么直接把A[0(i-2)]编辑成B[0(j-2)],即可，所以：
dp[i][j]=dp[i-1][j-1];

选出以上四种情况的最小值，就是最终dp[i][j]的值。

综上编写程序如下：

class MinCost {
public:
    int findMinCost(string A, int n, string B, int m, int c0, int c1, int c2) {
        // write code here
        int ic=c0,dc=c1,rc=c2;
        int dp[n+1][m+1];
        //先求第一行dp[0][j],将空串变成B[0...j-1],直接一个一个插入
        for(int j=0;j<m+1;j++)
        {
            dp[0][j]=j*ic;
        }
        //再求第一列，将A[0...i-1]变成空串,直接一个一个删除
        for(int i=0;i<n+1;i++)
        {
            dp[i][0]=i*dc;
        }
        //再求其他行,从上到下，从左往右计算
        for(int i=1;i<n+1;i++)
        {
            for(int j=1;j<m+1;j++)
            {
                int Min_Num=min(dc+dp[i-1][j],ic+dp[i][j-1]);
                if(A[i-1]!=B[j-1])
                {
                    Min_Num=min(rc+dp[i-1][j-1],Min_Num);
                }
                else
                {
                    Min_Num=min(dp[i-1][j-1],Min_Num);
                }   
                dp[i][j]=Min_Num;
            }
        }
        return dp[n][m];
        
    }
};