最小編輯代價

最小編輯代價問題：

對于兩個字符串A和B，我們需要進行插入、刪除和修改操作將A串變為B串，定義c0，c1，c2分別為三種操作的代價，請設計一個高效算法，求出將A串變為B串所需要的最少代價。

給定兩個字符串A和B，及它們的長度和三種操作代價，請返回將A串變為B串所需要的最小代價。保證兩串長度均小于等于300，且三種代價值均小于等于100。

測試樣例：

"abc",3,"adc",3,5,3,100

返回：8

問題分析：看到這道題，首先想到的是編輯距離問題，可以說是有異曲同工之處，但需要注意的是要將增刪改的代價考慮進去。

注意：（1）增刪的操作只能是在A串上操作，增加B[j]：h[i][j] = h[i][j-1]+c0；刪除A[i]：h[i][j] = h[i-1][j]+c1；

（2）修改的操作要比較代價大小，因為刪除一次再插入一次也可以看做是修改操作。

程序實現：

class MinCost {
public:
    int min2(int a,int b){
        return a<b?a:b;
    }
    int min3(int a,int b,int c){
        return min2(a,b)<c?min2(a,b):c;
    }
    int findMinCost(string A, int n, string B, int m, int c0, int c1, int c2) {
        // write code here
        int h[n+1][m+1];
        h[0][0] = 0;
        for(int i=1;i<=n;i++)
            h[i][0] = i * c1;
        for(int j=1;j<=m;j++)
            h[0][j] = j * c0;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                if(A[i-1] == B[j-1])
                    h[i][j] = h[i-1][j-1];
                else{
                    int Delete_cost = h[i-1][j] + c1;//刪除A[i]
                    int Insert_cost = h[i][j-1] + c0;//插入B[j]
                    int Modify_cost = h[i-1][j-1] + min2(c0+c1,c2);//修改A[i]為B[j]
                    h[i][j] = min3(Delete_cost,Insert_cost,Modify_cost);
                }
            }
        }
        return h[n][m];
    }
};

轉載請注明出處：

C++博客園：godfrey_88

http://www.cnblogs.com/gaobaoru-articles/