题解 | #编辑距离(二)#

package main

/**
 * min edit cost
 * @param str1 string字符串 the string
 * @param str2 string字符串 the string
 * @param ic int整型 insert cost
 * @param dc int整型 delete cost
 * @param rc int整型 replace cost
 * @return int整型
*/
func minEditCost(str1 string, str2 string, ic int, dc int, rc int) int {
	n := len(str1)
	m := len(str2)
	dp := make([][]int, n+1)
	for i := 0; i <= n; i++ {
		dp[i] = make([]int, m+1)
	}
	for i := 0; i <= n; i++ {
		for j := 0; j <= m; j++ {
			if i == 0 && j == 0 {
				dp[i][j] = 0
			} else if i > 0 && j == 0 {
				dp[i][j] = dp[i-1][j] + dc
			} else if i == 0 && j > 0 {
				dp[i][j] = dp[i][j-1] + ic
			} else {
				dp[i][j] = dp[i-1][j] + dc
				if dp[i][j-1] + ic < dp[i][j] {
					dp[i][j] = dp[i][j-1] + ic
				}
				val := dp[i-1][j-1]
				if str1[i-1] != str2[j-1] {
					 val += rc 
				}
				if val < dp[i][j] {
					dp[i][j] = val
				}
			}
		}
	}
	return dp[n][m]
	// write code here
}