题解 | #最小编辑代价#

dp解法的状态转移解释

int insert = dp[i][j-1] + 1; i个编辑成j-1个字符，再插入一个j
int delete = dp[i-1][j] + 1; i-1个编辑成j个字母，再删除一个i
int replace = dp[i-1][j-1] + 1; i-1个编辑成j-1个字母，再将i替换成j

#
# 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整型
#
class Solution:
    def minEditCost(self , str1 , str2 , ic , dc , rc ):
        # write code here
        m, n = len(str1), len(str2)
        dp = [[0 for i in range(n+1)] for j in range(m+1)]
        for i in range(m+1):
            dp[i][0] = dc*i
        for j in range(n+1):
            dp[0][j] = ic*j
        for i in range(1, m+1):
            for j in range(1, n+1):
                if str1[i-1] == str2[j-1]:
                    dp[i][j] = dp[i-1][j-1]
                else:
                    dp[i][j] = min(dp[i-1][j-1]+rc, dp[i][j-1]+ic, dp[i-1][j]+dc)
        return dp[m][n]