代码随想录第45天

115.不同的子序列

class Solution:def numDistinct(self, s: str, t: str) -> int:n1 = len(s)n2 = len(t)dp = [[0] * (n1 + 1) for _ in range(n2 + 1)]for j in range(n1 + 1):dp[0][j] = 1for i in range(1, n2 + 1):for j in range(1, n1 + 1):if t[i - 1] == s[j - 1]:dp[i][j] = dp[i - 1][j - 1]  + dp[i][j - 1]else:dp[i][j] = dp[i][j - 1]#print(dp)return dp[-1][-1]

583. 两个字符串的删除操作

class Solution:def minDistance(self, word1: str, word2: str) -> int:m, n = len(word1), len(word2)dp = [[0] * (n + 1) for _ in range(m + 1)]for i in range(m):for j in range(n):if word1[i] == word2[j]:dp[i+1][j+1] = dp[i][j] + 1else:dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j])return m + n - dp[m][n] * 2

72. 编辑距离

class Solution:def minDistance(self, word1: str, word2: str) -> int:n = len(word1)m = len(word2)# 有一个字符串为空串if n * m == 0:return n + m# DP 数组D = [ [0] * (m + 1) for _ in range(n + 1)]# 边界状态初始化for i in range(n + 1):D[i][0] = ifor j in range(m + 1):D[0][j] = j# 计算所有 DP 值for i in range(1, n + 1):for j in range(1, m + 1):left = D[i - 1][j] + 1down = D[i][j - 1] + 1left_down = D[i - 1][j - 1] if word1[i - 1] != word2[j - 1]:left_down += 1D[i][j] = min(left, down, left_down)return D[n][m]