力扣 72. 编辑距离 python AC

动态规划

class Solution:def minDistance(self, word1, word2):size1 = len(word1)size2 = len(word2)dp = [[0] * (size2 + 1) for _ in range(size1 + 1)]for i in range(1, size1 + 1):dp[i][0] = dp[i - 1][0] + 1for i in range(1, size2 + 1):dp[0][i] = dp[0][i - 1] + 1for i in range(1, size1 + 1):for j in range(1, size2 + 1):if word1[i - 1] == word2[j - 1]:dp[i][j] = dp[i - 1][j - 1]else:dp[i][j] = min(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]) + 1return dp[size1][size2]

定义状态dp[i][j]为：字符串1到第i位为止转化成字符串2到第j位为止需要的最少操作数

--初始化二维数组dp：size1+1行size2+1列

--处理边界：第0行/第0列表示空字符串1转化为字符串2/字符串1转化为空字符串2需要的操作数

（索引每+1，操作数+1，（需要增加/删去它长度次））

--从1到size1遍历i

  --从1到size2遍历j

    --如果字符串1第i位和字符串2第j位相等

      --dp[i][j] 和 dp[i - 1][j - 1] 相同（需要操作次数相同）

    --否则

      --dp[i][j] 为 dp[i - 1][j - 1]（替换） dp[i - 1][j]（删除）dp[i][j - 1] （插入）三者中的最小值 + 1