编辑距离(二)

问题简述

给定两个字符串str1和str2，再给定三个整数ic，dc和rc，分别代表插入、删除和替换一个字符的代价，请输出将str1编辑成str2的最小代价。

编辑距离(二)_牛客题霸_牛客网

思路：动态规划

• 定义 dp(i, j) 表示将 s1[:i] 编辑到 s2[:j] 的最小代价；

写法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
        import sys
        sys.setrecursionlimit(10000)
        
        from functools import lru_cache
        
        @lru_cache(maxsize=None)
        def dp(i, j):
            if i == 0 and j == 0: return 0
            if i == 0: return ic * j
            if j == 0: return dc * i
            
            r1 = dp(i - 1, j) + dc
            r2 = dp(i, j - 1) + ic
            r3 = dp(i - 1, j - 1)
            if str1[i - 1] != str2[j - 1]:
                r3 += rc
            
            return min(r1, r2, r3)
        
        return dp(len(str1), len(str2))

优化：可以看到，想让递归代码通过所有用例，需要解除递归深度限制，还有用上记忆化搜素；下面是把递归代码一比一修改为标准动态规划写法的代码；

写法2：动态规划

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 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
        
        m, n = len(str1), len(str2)
        dp = [[0] * (n + 1) for _ in range(m + 1)]
        
        for i in range(m + 1):
            for j in range(n + 1):
                if i == 0: 
                    dp[i][j] = ic * j
                    continue
                if j == 0: 
                    dp[i][j] = dc * i
                    continue
                r1 = dp[i - 1][j] + dc
                r2 = dp[i][j - 1] + ic
                r3 = dp[i - 1][j - 1]
                if str1[i - 1] != str2[j - 1]:
                    r3 += rc
                dp[i][j] = min(r1, r2, r3)
        
        return dp[-1][-1]