目录
任务
115. 不同的子序列
给你两个字符串 s 和 t ，统计并返回在 s 的 子序列 中 t 出现的个数，结果需要对 10^9 + 7 取模。
思路
dp[i][j]表示s[0:i)中出现以t[0,j)的次数
每次拓展一个字符，求次数，直到拓展完成，分为两种情况
- 当当前字符相等时，即s[i-1] == t[j-1] 时，次数等于两种情况相加，一种是用s[i-1]来匹配这个字符，即之前满足条件的次数；第二种是不用s[i-1]来匹配这个字符，满足条件的次数
- 当当前字符不等时，次数等于s去掉这个字符，满足条件的次数
注意初始化的情况
class Solution:
def numDistinct(self, s: str, t: str) -> int:
#dp[i][j] 表示s[0:i)中出现以t[0,j)的次数
dp = [[0] * (len(t)+1) for _ in range(len(s)+1)]
for j in range(len(t)+1): #初始化第一行（s为空的情况）
dp[0][j] = 0
for i in range(len(s)+1): #初始化第一列(t为空的情况)
dp[i][0] = 1
for 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)]
583. 两个字符串的删除操作
给定两个单词 word1 和 word2 ，返回使得 word1 和 word2 相同所需的最小步数。
每步 可以删除任意一个字符串中的一个字符。
思路
dp[i][j] 表示只是用删除操作使得word1[0:i)中word2[0,j)相同的最小次数
每次拓展一个字符，求次数，直到拓展完成，分为两种情况
- 当当前字符相等时，即s[i-1] == t[j-1] 时，不需要删除，操作数不变，即次数延续拓展字符之前的情况
- 当当前字符不等时，有三种情况处理，第一种是删除word1中的元素，第二种情况是删除word2中的元素，第三种情况是同时删除word1,word2中的元素，求这三种情况的最小值即可，实际上，可以忽略第三种情况，因为它可以由前两种情况推导得到
class Solution:
def minDistance(self, word1: str, word2: str) -> int:
#dp[i][j] 表示只是用删除操作使得word1[0:i)中word2[0,j)相同的最小次数
dp = [[0] * (len(word2)+1) for _ in range(len(word1)+1)]
for j in range(len(word2)+1): #初始化第一行，即word1为空的情况
dp[0][j] = j
for i in range(len(word1)+1):
dp[i][0] = i
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]
else:
dp[i][j] = min(dp[i-1][j] + 1, # 当前删除word1[i-1],所以操作的最小次数为使得word1[0:i-1)中word2[0,j)相同的最小次数加上这次删除（1次）的总次数
dp[i][j-1] + 1, # 当前删除word2[i-1]
#dp[i-1][j-1] + 2 # 同时删除word1[i-1]，word2[i-1]，实际可以不需要，因为可以从前两步推导出来
)
return dp[len(word1)][len(word2)]
72. 编辑距离
给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数 。
你可以对一个单词进行如下三种操作：
插入一个字符
删除一个字符
替换一个字符
思路
由于插入和删除是镜像操作（删除word1中的元素相当于添加word2中的元素），所以只考虑删除。类比583. 两个字符串的删除操作
- 当前字符相等时，操作数不变
- 当前字符不同时，有三种情况（删除两种，替换一种），前两种同583. 两个字符串的删除操作，并且隐含同时删除的情况。第三种替换，即将当前的字符替换，为之前的情况(dp[i-1]dp[j-1])增加一次即可
class Solution:
def minDistance(self, word1: str, word2: str) -> int:
#dp[i][j] 表示用删除，添加，替换操作使得word1[0:i)中word2[0,j)相同的最小次数
dp = [[0] * (len(word2)+1) for _ in range(len(word1)+1)]
for j in range(len(word2)+1): #初始化第一行，即word1为空的情况
dp[0][j] = j
for i in range(len(word1)+1):
dp[i][0] = i
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]
else:
dp[i][j] = min(dp[i-1][j] + 1, # 当前删除word1[i-1]，相当于在word2中添加
dp[i][j-1] + 1, # 当前删除word2[i-1]，相当于在word1中添加
dp[i-1][j-1] + 1 # 由于当前元素不同，替换当前元素，让word1[i-1] == word2[j-1]
)
return dp[len(word1)][len(word2)]