代码随想录算法训练营四十五天|115.不同的子序列、583.两个字符串的删除操作、72.编辑距离
题目链接：115. 不同的子序列 - 力扣（LeetCode）
class Solution(object):def numDistinct(self, s, t):""":type s: str:type t: str:rtype: int"""dp = [[0] * (len(t) + 1) for _ in range(len(s) + 1)]for i in range(len(s) + 1):dp[i][0] = 1for i in range(1, len(s) + 1):for j in range(1, len(t) + 1):if s[i-1] == t[j-1]:dp[i][j] = dp[i-1][j-1] + dp[i-1][j]else:dp[i][j] = dp[i-1][j]return dp[len(s)][len(t)]题目链接：1143. 最长公共子序列 - 力扣（LeetCode）
思路：算出公共子序列的最大长度，那么用两个字符串的长度减去公共的部分，就得到了需要操作的最少步数
class Solution(object):def minDistance(self, word1, word2):""":type word1: str:type word2: str:rtype: int"""result = 0dp = [[0] * (len(word2) + 1) for _ in range(len(word1) + 1)]for i in range(1, len(word1) + 1):for j in range(1, len(word2) + 1):if word1[i-1] == word2[j-1]:dp[i][j] = dp[i-1][j-1] + 1else:dp[i][j] = max(dp[i-1][j], dp[i][j-1])result = dp[i][j] if dp[i][j] > result else dp[i][j]return len(word2) + len(word1) - 2 * result题目链接：72. 编辑距离 - 力扣（LeetCode）
思路：思路跟之前求公共子序列差不多 分为dp[i-1] == dp[j-1] 的情况 和dp[i-1] != dp[j-1]的情况 不等于的情况下分为三种 1.修改一个字符 2.删除一个字符 3.添加一个字符 并取其中的最小值。
class Solution(object):def minDistance(self, word1, word2):""":type word1: str:type word2: str:rtype: int"""dp = [[0] * (len(word2) + 1) for _ in range(len(word1) + 1)]for i in range(len(word2) + 1):dp[0][i] = ifor i in range(len(word1) + 1):dp[i][0] = ifor i in range(1, len(word1) + 1):for j in range(1, len(word2) + 1):if word1[i - 1] == word2[j - 1]:dp[i][j] = dp[i-1][j-1]else:# 删除# 添加# 修改dp[i][j] = min(min(dp[i-1][j-1] + 1, dp[i-1][j] + 1), dp[i][j-1] + 1)return dp[len(word1)][len(word2)]