动态规划做法

之前做过类似的题目，那个题目中插入、删除、替换的代价都是相同的，都是1，在这个题目里面是不同的。

理解的时候需要注意，是要由str1变成str2。变化情况分三种，对str1进行插入，对str1进行删除，对str1进行替换。
dp数组的i行j列代表str1的前i个字符编辑成str2的前j个字符的最小代价。
假设str1的第i个字符和str2的第j个字符匹配，dp[i][j]=dp[i-1][j-1]，因为str1的前i-1个字符已经和str2的前j-1个字符相同了。
当str1的第i个字符和str2的第j个字符不匹配时，三种选择，对str1的字符进行1）删除、2）插入、与3）替换，这些操作都是发生在str1上。
1）删除。将str1的第i个字符删除，删除这一个字符，那怎么让str1变成str2啊？这时我们就寄希望于str1的前i-1个字符和str2的前j个字符相同了，将str1的前i-1个字符变成str2的前j个字符的代价已经求出了，就是dp[i-1][j]，所以删除str1的第i个字符，str1的前i个字符还能和str2的前j个字符相同的代价就是dp[i-1][j]+dc。
2）插入。在str1的第i个位置后进行插入，使得str1的前i个字符和str2的前j个字符相同，那得要求str1的前i个字符和str2的前j-1个字符相同啊，这时候再进行插入，也就是将str2的第j个字符插入到str1的第i个字符之后。此时编辑代价为dp[i][j-1]+ic。
3）替换。替换好解释，就是str1的前i-1个字符变成str2的前j个字符的代价，加上将str1的第i个字符替换为str2的第j个字符的代价。dp[i-1][j-1]+rc。

class Solution:
    def minEditCost(self , str1 , str2 , ic , dc , rc ):
        m,n=len(str1),len(str2)
        dp=[[0]*(n+1) for _ in range(m+1)]
        for i in range(m+1):
            dp[i][0]=i*dc
        for j in range(n+1):
            dp[0][j]=j*ic
        for i in range(1,m+1):
            for j in range(1,n+1):
                cost = 0 if str1[i-1]==str2[j-1] else rc
                dp[i][j]=min(dp[i-1][j]+dc,dp[i][j-1]+ic,dp[i-1][j-1]+cost)
        return dp[m][n]