python动态规划解法

不知为啥爆内存， 这是python标准的动态规划解法了。
相较于原始的编辑距离题目（插入，删除，替换代价相同），这道题插入，删除，替换的代价不同。不过难度并没有多大提升。
如果还不会原始题目的动态规划解法，建议先去弄懂（把三种方式的代价固定为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 , str2 , ic , dc , rc ):
        # str1为空时，插入lens2个字符得到str2
        # str2为空时，删除lens1个字符得到str1
        lens1, lens2 = len(str1), len(str2)
        if lens1 == 0: return lens2 * ic
        if lens2 == 0: return lens1 * dc

        # 初始化dp数组
        dp = [[0] * lens2 for _ in range(lens1)]

        dp[0][0] = 0 if str1[0] == str2[0] else rc
        # str2长度增加时，由str1[0]得到str2需要不断插入
        for i in range(1, lens2):
            dp[0][i] = dp[0][i-1] + ic
        # str1长度增加时， 由str1得到str2[0]需要不断删除
        for i in range(1, lens1):
            dp[i][0] = dp[i-1][0] + dc

        # 主循环
        for i in range(1, lens1):
            for j in range(1, lens2):
                # 两个字符相同时，在dp[i-1][j-1]的基础上不需要代价，否则需要替换一个字符
                cost = 0 if str1[i] == str2[j] else rc
                dp[i][j] = min(dp[i-1][j-1] + cost,  # 在dp[i-1][j-1]的基础上替换/不替换字符
                               dp[i-1][j] + dc,  # 在dp[i-1][j]的基础上删除一个字符
                               dp[i][j-1] + ic)  # 在dp[i][j-1]的基础上插入一个字符
        return dp[lens1-1][lens2-1]