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

【二维dp】

观察题意，考点主要是编辑距离，基本可以确定使用dp

本文明确要求str1转化到str2，所以在初始化时需要注意，i>j时，必须dc；i<j时，必须ic

当两个对应的字符相等时，dp[i][j]=dp[i-1][j-1]

当不相等时，则需要找到一种最小的变化方式，dp[i][j]=min(dp[i-1][j-1]+rc,dp[i][j-1]+ic,dp[i-1][j]+dc)，要么在str1[:i-1]和str2[:i-1]的基础上进行替换(+rc)；要么在str1[:i]和str2[:j-1]的基础上进行插入(+ic)；要么根据str1[:i-1]和str2[:j]的结果进行删除(+dc)

最后返回dp[-1][-1]

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 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:
        # write code here
        #dp表示对应位置最小代价
        dp=[[0 for _ in range(len(str2)+1)] for _ in range(len(str1)+1)]
        for i in range(1,len(str2)+1):
            dp[0][i]=dp[0][i-1]+ic
        for i in range(1,len(str1)+1):
            dp[i][0]=dp[i-1][0]+dc
        
        for i in range(1,len(str1)+1):
            for j in range(1,len(str2)+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[-1][-1]