二维动态规划，设置二维数组 dp 表示 str1[:i + 1] -> str2[:j + 1] 所用的最小操作数 则 (1) 初始值为: dp[0][0] = 0 即 str1 = "" 和 str2 = "" 时的情况 dp[i][0] 表示 str1 变为 str2 = "" 需要编辑的操作数,由于限定 j = 0 则 dp[i][0] 只能由 dp[i - 1][0] 转移过来, 即str1[:i] 已与 "" 匹配,则删除 str1[i] 的值达到匹配 dp[0][j] 表示 str1 = "" 变为 str2 需要编辑的操作数,由于限定 i = 0 则 dp[0][i] 只能由 dp[0][i - 1] 状态转移过来,即 str1[i] = "" 增加 str2[j]的值达到匹配 (2) 转移方程为: 当 str1[i] == str2[j] 时, dp[i][j] = dp[i - 1][j - 1] 当 str1[i] != str2[j] 时, 由于要求的是最小编辑距离,则 dp[i][j] 从上一个符合匹配条件的状态转移过来，即 dp[i - 1]j: 因为 str1[:i] 与 str2[:j + 1] 匹配, str1[i] 有值, str2 无 则删除str1[i]的值 dp[i][j - 1] (增加值): 因为 str1[:i + 1] 与 str2[:j] 匹配, str1[i] != str2[j], str2[j] 有值, str1 无值,插入str2[j] 的值 dp[i - 1][j - 1] (替换值): str1[:i] 与 str2[:j] 匹配, str1[i] != str2[j], str1[i] 和 str2[j] 均有值,替换该值 这三个操作中取距离最小的,再加上当前的操作数

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param str1 string字符串 
# @param str2 string字符串 
# @return int整型
#
class Solution:
    def editDistance(self , str1: str, str2: str) -> int:
        # write code here
        dp = [[0 for _ in range(len(str2) + 1)] for _ in range(len(str1) + 1)]
        for i in range(1, len(str1) + 1):
            dp[i][0] = dp[i - 1][0] + 1
        for i in range(1, len(str2) + 1):
            dp[0][i] = dp[0][i - 1] + 1
        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 - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1
        return dp[-1][-1]