题解 | #最小编辑代价#

解题思路：
动态规划
1.dp[i][j]定义
字符串str1[0~i]编辑成字符串str2[0~j]的需要的最小编辑代价
2.状态转移方程
当str2[i] == str1[j]，dp[i][j] = dp[i-1][j-1] 
当str2[i] != str1[j]，dp[i][j] = min(dp[i][j-1]+ic, dp[i-1][j]+dc, dp[i-1][j-1]+rc)    # 插入、删除、替换比小 
3.边界
dp[0][0] = 0
dp[0][j] = j*ic，j次插入
dp[i][0] = i*dc，i次删除
#=============================================================================================
'''
#
# 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
        r = len(str1)
        c = len(str2)
        dp = [[0]*(c+1) for _ in range(r+1)]

        for i in range(r+1):
            for j in range(c+1):
                if i==0 and j==0:
                    dp[i][j]=0
                elif i==0:          
                    dp[0][j] = j*ic        # j变化插入操作
                elif j==0:         
                    dp[i][0] = i*dc        # i变量删除操作
                else:
                    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)    # 插入、删除、替换比小 
        for i in dp:
            print(i)
        return dp[-1][-1]

s = Solution()
str1 = 'abc'
str2 = 'adc'
ic = 5
dc = 3
rc = 100
print(s.minEditCost(str1,str2,ic,dc,rc))