题解 | #最小编辑代价#

class Solution:
    def minEditCost(self , str1 , str2 , ic , dc , rc ):
        # write code here
        len1, len2 = len(str1), len(str2)
        dp = [[0 for _ in range(len2 + 1)] for _ in range(len1 + 1)]
        for i in range(1, len1 + 1):
            dp[i][0] = i * dc
        for i in range(1, len2 + 1): # 注意，和下面的删除操作一致
            dp[0][i] = i * ic
        for i  in range(len1):
            for j in range(len2):
                if str1[i] == str2[j]:
                    dp[i + 1][j + 1] = dp[i][j]
                else:
                    dp[i + 1][j + 1] = min(dp[i][j] + rc, dp[i + 1][j] + ic, dp[i][j + 1] + dc)
        return dp[len1][len2]