编辑距离 -- 动规

72. 编辑距离

给出动规的两种常见实现形式：自顶向下、自底向上，前者一般借助递归函数+备忘录实现，后者通常基于dp数组实现。

class MinDistance:"""72. 编辑距离https://leetcode.cn/problems/edit-distance/"""def solution(self, s1: str, s2: str) -> int:"""递归解法 + 备忘录自顶向下:param s1::param s2::return:"""#  memo[i][j] 表示 s1[0..i] 和 s2[0..j] 的最⼩编辑距离m, n = len(s1), len(s2)self.memo = [[-1 for _ in range(n)] for _ in range(m)]return self.dp(s1, m-1, s2, n-1)def dp(self, s1, i, s2, j):"""自顶向下:param s1::param i::param s2::param j::return: s1[0..i] 和 s2[0..j] 的最⼩编辑距离"""# base caseif i == -1:return j+1if j == -1:return i+1if self.memo[i][j] != -1:return self.memo[i][j]if s1[i] == s2[j]:self.memo[i][j] = self.dp(s1, i-1, s2, j-1)else:self.memo[i][j] = min(self.dp(s1, i-1, s2, j) + 1,  # 删除self.dp(s1, i, s2, j-1) + 1,  # 插入self.dp(s1, i-1, s2, j-1) + 1,  # 替换)return self.memo[i][j]def solution2(self, s1: str, s2: str) -> int:"""dp table自底向上 求解:param s1::param s2::return:"""#  dp[i+1][j+1] 表示 s1[0..i] 和 s2[0..j] 的最⼩编辑距离m, n = len(s1), len(s2)dp = [[-1 for _ in range(n+1)] for _ in range(m+1)]# base casefor i in range(m+1):dp[i][0] = ifor j in range(n+1):dp[0][j] = jfor i in range(1, m+1):for j in range(1, n+1):if s1[i-1] == s2[j-1]:dp[i][j] = dp[i-1][j-1]else:dp[i][j] = min(dp[i - 1][j - 1] + 1,dp[i][j - 1] + 1,dp[i - 1][j] + 1)return dp[m][n]