前言
今天我們繼續(xù)討論經(jīng)典的動(dòng)態(tài)規(guī)劃問題之最小編輯距離問題。
最小編輯距離問題
問題描述
對(duì)于兩個(gè)字符串A和B，我們需要進(jìn)行插入腰湾、刪除和修改操作將A串變?yōu)锽串，定義c0疆股，c1费坊，c2分別為三種操作的代價(jià)，請(qǐng)?jiān)O(shè)計(jì)一個(gè)高效算法旬痹，求出將A串變?yōu)锽串所需要的最少代價(jià)附井。例如將"abc"轉(zhuǎn)化為"adc"，c0=5两残，c1=3永毅，c2=100，最小代價(jià)為8人弓。
問題分析
我們先解釋下問題描述中為什么最小代價(jià)是8沼死。如果插入、刪除和修改操作的代價(jià)相同崔赌，顯然意蛀，"abc"->"adc"直接將'b'->'d'即可。但是由于多了c0=5健芭，c1=3县钥，c2=100的條件，所以直接進(jìn)行修改操作其代價(jià)為100慈迈，顯然不是最小代價(jià)若贮。最小代價(jià)對(duì)應(yīng)的操作應(yīng)該是使用插入、刪除操作代替修改操作——先在'a'與'c'中插入'd'痒留，然后刪除'b'谴麦，或者先刪除'b'，在插入'd'狭瞎。這樣最小代價(jià)為8细移。
其實(shí)，該問題實(shí)質(zhì)上是求解的最小編輯距離熊锭，只不過對(duì)每種操作賦予了權(quán)值弧轧。假設(shè)兩字符串A和B的長(zhǎng)度分別為
和
。我們需要構(gòu)建一個(gè)
的矩陣
碗殷，代表
的最小代價(jià)為
精绎。可能你會(huì)疑問锌妻，為什么是
代乃，而不是
呢? 觀察下面的矩陣，你可能會(huì)找到答案。我們需要在兩字符串前添加空字符串來得到增加搁吓、刪除操作所對(duì)應(yīng)的代價(jià)作為初始值原茅。
| '' | 'a' | 'd' | 'c' | |
|---|---|---|---|---|
| '' | 0 | 5 | 10 | 15 |
| 'a' | 3 | |||
| 'b' | 6 | |||
| 'c' | 9 |
對(duì)于矩陣第0行第0列，代表由堕仔，顯然代價(jià)為0擂橘，即
;
對(duì)于矩陣第0行第1列，代表由摩骨，其代價(jià)為
通贞，即
;
對(duì)于矩陣第0行第2列，代表由恼五，其代價(jià)為
昌罩，即
;
依次類推，茎用。
同樣的，對(duì)于绘搞。
那么當(dāng) 時(shí)，
下面傅物，我們分兩種情況進(jìn)行討論：
(1) 當(dāng) 時(shí)夯辖，可能的操作即最小代價(jià)有以下幾種情況：
- 不需要進(jìn)行任何操作，此時(shí)最小代價(jià)就是
的最小代價(jià)董饰，即
蒿褂；
- 先
，然后增加
卒暂，此時(shí)最小代價(jià)為
啄栓，即
；
- 先將
也祠，然后刪除
昙楚，此時(shí)最小代價(jià)為
，即
诈嘿。
此時(shí)堪旧，;
(2) 當(dāng) 時(shí)，可能的操作即最小代價(jià)有以下幾種情況：
- 直接將A[i]替換為B[j]奖亚，此時(shí)最小代價(jià)就是
淳梦，即
；
- 先
- 先將
此時(shí)挂捅，;
需要注意的是，當(dāng)時(shí)堂湖，需要令
，這是因?yàn)樾薷牟僮骺梢杂迷黾?刪除操作代替状土，這樣的代價(jià)比直接進(jìn)行修改操作的代價(jià)要低无蜂。問題分析一開始也給出了說明。
代碼實(shí)現(xiàn)
通過問題分析蒙谓，可以很容易得用代碼實(shí)現(xiàn)斥季，下面給出算法的java實(shí)現(xiàn)。
public class MinCost {
public int findMinCost(String A, int n, String B, int m, int c0, int c1, int c2) {
return core(A, n, B, m, c0, c1, c2);
}
public int core(String A, int n, String B, int m, int c0, int c1, int c2) {
if (A.length() == 0 || B.length() == 0) {
return 0;
}
A = " " + A;
B = " " + B;
int[][] dp = new int[n + 1][m + 1];
// 初始化第0行
dp[0][0] = 0;
for (int i = 1; i < m + 1; i++) {
dp[0][i] = c0 * i;
}
// 初始化第0列
for (int j = 1; j < n + 1; j++) {
dp[j][0] = c1 * j;
}
//update=delete+insert,如果update花費(fèi)更多就用delete+insert的花費(fèi)之和替換
if (c2 >= c0 + c1) {
c2 = c0 + c1;
}
for (int i = 1; i < n + 1; i++) {
for (int j = 1; j < m + 1; j++) {
if (A.charAt(i) == B.charAt(j)) {
//如果兩個(gè)字符串中A[i],B[j]的字符都一樣的
//1.什么都不做就行累驮，0操作
int dontChange = dp[i - 1][j - 1];
//2.比如由abd→abcd=abc→ab+B串刪除c
int delete = dp[i - 1][j] + c1;
//3.比如由abcd→abcd=abcd→abc+B串插入d
int insert = dp[i][j - 1] + c0;
dp[i][j] = Math.min((Math.min(dontChange, delete)), insert);
} else {
//1. A abcd → B abce = A abc→B abc + (A abcd → B abce, 替換d為e)
int replace = dp[i - 1][j - 1] + c2;
//2.比如由A abcd→B abce=A abc→B abce+B串刪除e
int delete = dp[i - 1][j] + c1;
//3.比如由A abcd→B abce=A abcd→B abc+B串插入d
int insert = dp[i][j - 1] + c0;
dp[i][j] = Math.min((Math.min(replace, delete)), insert);
}
}
}
return dp[n][m];
}
public static void main(String[] args) {
MinCost minCost = new MinCost();
String A = "abc";
int n = A.length();
String B = "adc";
int m = B.length();
int c0 = 3;
int c1 = 5;
int c2 = 3;
int res = minCost.findMinCost(A, n, B, m, c0, c1, c2);
System.out.println(res);
}
}
經(jīng)典問題
- 算法思想之動(dòng)態(tài)規(guī)劃(二)——最小路徑和問題
- 算法思想之動(dòng)態(tài)規(guī)劃(三)——找零錢問題
- 算法思想之動(dòng)態(tài)規(guī)劃(四)——最長(zhǎng)公共子序列問題
- 算法思想之動(dòng)態(tài)規(guī)劃(六)——最長(zhǎng)上升子序列問題
- 算法思想之動(dòng)態(tài)規(guī)劃(七)——背包問題
未來幾篇博文酣倾，我將繼續(xù)對(duì)經(jīng)典的動(dòng)態(tài)規(guī)劃問題進(jìn)行整理，敬請(qǐng)關(guān)注~
由于本人水平有限谤专，文章難免有欠妥之處躁锡，歡迎大家多多批評(píng)指正！
寫在最后
歡迎大家關(guān)注我的個(gè)人博客復(fù)旦猿置侍。
