题解 | #最小编辑代价#

题目要求s1 通过增、删、替换的方式以最小的操作数变成 s2,即两个字符串比较求极值,由两个字符串和比较等特点分析应该可采用递归的方式的处理,即 func(s1[i], s2[j]) 对两个字符串的每个字符进行比较,直到 i、j 取完,当 s1[i] == s2[j] 直接递归 s1[i - 1] s2[j - 1] 而当 s1[i] != s2[j] 时,则有三种方式可选,即三条路径,存在重叠子问题，可采用动态规划的方式求解

1. 定义 dp 数组，因为是两个字符串,则定义二维数组 dp[i][j] 表示 s1[:i + 1] 变成 s2[:j + 1] 的最小操作数
2. 定义 base case, dp[0][i] 表示 s1 = '' 时变成 s2 的最小步数,即每次都增加一个字符, dp[i][0] 表示 s2 = '' 时 s1 变成 s2的最小步数,即每次都减少一个字符
3. 确定状态转移方程, 即求解 dp[i][j] 的生成过程
   (1) s1[i] == s2[j] 时,dp[i][j] = dp[i - 1][j - 1] 不需要额外操作
   (2) s1[i] != s2[j] 时,dp[i][j] 可以从三个状态转移
   1) dp[i - 1][j] + dc 表示 s1[:i] 匹配 s2[:j + 1] 此时 s1[i] 多余删除
   2）dp[i][j - 1] + ic 表示 s1[:i + 1] 匹配 s2[:j] 此时插入 s2[j]
   3) dp[i - 1][j - 1] + rc 表示 s1[:i] 匹配 s2[:j] 替换 s1[i] 和 s2[j]的值
   这样自底向上的求出s1变成s2的最小操作数
   代码:

   class Solution:
    def minEditCost(self , str1 , str2 , ic , dc , rc ):
        # write code here
        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][j - 1] + ic, dp[i - 1][j] + dc, dp[i - 1][j - 1] + rc)
        return dp[-1][-1]