最小編輯代價-golang

題目：

給定兩個字符串str1和str2，在給定三個整數ic,dc和rc,分別代表插入、刪除和替換一個 字符，返回將str1編輯成str2的最小代價。

解題方法：

動態規劃。首先生成大小為(M+1)X(N+1)的矩陣dp。

假設str1="av=b12cd3", str2="abcdf"。dp[i][j]表示str1[0:i]編輯成str2[0:j]的最小代價。計算結果如下：

計算步驟：

1、dp[0][0]表示str1空的子串編輯成str2空的子串的代價為0

2、矩陣dp第一列即dp[0:M-1][0], dp[i][0] 表示str1[0:i-1]編輯成空串的最小代價，即把str1[0:i-1]中所有字符刪掉的代價，所以dp[i][0] = dc * i

3、矩陣第一行即dp[0][0:N-1], dp[0][j]表示空串編輯成str2[0:j-1]的最小代價，即向空串中添加字符的代價，所以dp[0][j] = ic * j

4、其他位置，從左到右，從上到下計算，dp[i][j]的值可能來自于一下四種情況：

（1）str1[0:i-1]先編輯成str1[0:i-2]，即先刪除字符str1[i]，然后由str1[0:i-2]編輯成str2[0:j-1],dp[i-1][j] 表示str1[0:i-2]編輯成石頭人[0:j-1]的最小代價，那么dp[i][j]可能等于dc + dp[i-1][j]

（2）str1[0:i-1]可以先編輯成str2[0:j-2],然后向str2[0:j-2]插入字符str2[j-1],編輯成str2[0:j-1]，dp[i][j-1]表示str1[0:i-1]編輯成str2[0:j-2]的最小代價，那么dp[i][[j]可能等于dp[i][j-1] + ic;

? (3) 如果str1[i-1] != str2[j-1], 可以先將str1[0:i-2]編輯成str2[0:j-2],然后將str1[i-1]替換成str2[j-1]，dp[i-1][j-1]表示將str1[0:i-2]編輯成str2[0:j-2]的最小代價，那么dp[i][j]可能等于dp[i-1][j-1]+rc

（4）如果str1[i-1] == str2[j-1], 則此時dp[i][j] = dp[i-1][j-1]

具體代碼如下：

func GetDp(str1, str2 []rune, ic, dc, rc int)int{rows := len(str1) + 1cols := len(str2) + 1dp := make([][]int, rows)for i, _ := range dp {dp[i] = make([]int, cols)}for i:=0;i < cols;i++{dp[0][i] = ic * i}for i:=0;i < rows;i++{dp[i][0] = dc * i}for i:=1;i<rows;i++{for j:=1;j<cols;j++{if str1[i-1] == str2[j-1]{dp[i][j] = dp[i-1][j-1]}else{dp[i][j] = dp[i-1][j-1] + rc}dp[i][j] = getMin(dp[i][j], dp[i][j-1]+ic)dp[i][j] = getMin(dp[i][j], dp[i-1][j] + dc)}}return dp[rows-1][cols-1]
}