机试刷题_编辑距离(二)【python】

题目：编辑距离(二)

描述
给定两个字符串str1和str2，再给定三个整数ic，dc和rc，分别代表插入、删除和替换一个字符的代价，请输出将str1编辑成str2的最小代价。

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 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: str, str2: str, ic: int, dc: int, rc: int) -> int:
        # 动态规划
        n = len(str1)
        m = len(str2)
        dp = [[0]*(m+1) for i in range(n+1)]
        # str2为0，只能删除
        for i in range(n+1):
            dp[i][0] = i*dc
        # str1为0，只能插入
        for j in range(m+1):
            dp[0][j] = j*ic
        for i in range(1,n+1):
            for j in range(1,m+1):
                if str1[i-1] == str2[j-1]:
                    dp[i][j] = dp[i-1][j-1]
                else:
                    dp[i][j] = min(dp[i][j-1]+ic,dp[i-1][j]+dc,dp[i-1][j-1]+rc)
        return dp[n][m]