1.不同的子序列
状态转移公式
对于 s[i-1] 和 t[j-1]：
如果 相等：
可以选择用这两个字符匹配（
dp[i-1][j-1]）也可以选择不用 s[i-1]（
dp[i-1][j]）因此：
dp[i][j]=dp[i−1][j−1]+dp[i−1][j]dp[i][j] = dp[i-1][j-1] + dp[i-1][j]dp[i][j]=dp[i−1][j−1]+dp[i−1][j]
如果 不相等：
只能跳过 s[i-1]：
dp[i][j]=dp[i−1][j]dp[i][j] = dp[i-1][j]dp[i][j]=dp[i−1][j]
class Solution:
def numDistinct(self, s: str, t: str) -> int:
#dp[i][j] 表示以下标i-1结尾的s子序列出现以j-1为结尾的t的个数是dp[i][j]
m = len(s)
n = len(t)
if m < n:
return 0
dp = [[0]*(n+1) for _ in range(m+1)]
for i in range(m):
dp[i][0] = 1
for j in range(1, n+1):
dp[0][j] = 0
for i in range(1, m+1):
for j in range(1, n+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[-1][-1]
2.两个字符串的删除操作
583. 两个字符串的删除操作 - 力扣（LeetCode）
思路：
1. 状态定义
dp[i][j] 表示：
word1前 i 个字符 和word2前 j 个字符 变成相同字符串所需的最少删除次数。
2. 初始化
dp[i][0] = i：如果word2是空串，只能删除word1的所有 i 个字符。dp[0][j] = j：如果word1是空串，只能删除word2的所有 j 个字符。
3. 状态转移
如果
word1[i-1] == word2[j-1]末尾字符相同，不需要额外操作：
dp[i][j]=dp[i−1][j−1]dp[i][j] = dp[i-1][j-1]dp[i][j]=dp[i−1][j−1]
如果
word1[i-1] != word2[j-1]删除
word1[i-1]：dp[i-1][j] + 1删除
word2[j-1]：dp[i][j-1] + 1同时删除两个末尾字符：
dp[i-1][j-1] + 2取最小值：
dp[i][j]=min(dp[i−1][j]+1, dp[i][j−1]+1, dp[i−1][j−1]+2)dp[i][j] = \min(dp[i-1][j] + 1,\ dp[i][j-1] + 1,\ dp[i-1][j-1] + 2)dp[i][j]=min(dp[i−1][j]+1, dp[i][j−1]+1, dp[i−1][j−1]+2)
4. 返回结果
dp[m][n]即为将word1和word2变成相同所需的最少删除步数。
class Solution:
def minDistance(self, word1: str, word2: str) -> int:
#dp[i][j] 表示以i-1结尾的word1子序列和以j-1结尾的word2子序列中使其相同的的最小步数是dp[i][j]
m = len(word1)
n = len(word2)
dp = [[0]*(n+1) for _ in range(m+1)]
for i in range(m+1):
dp[i][0] = i
for j in range(1, n+1):
dp[0][j] = j
for i in range(1, m+1):
for j in range(1, n+1):
if word1[i-1] != word2[j-1]:
dp[i][j] = min(dp[i-1][j]+1, dp[i][j-1]+1, dp[i-1][j-1]+2)
else:
dp[i][j] = dp[i-1][j-1]
return dp[-1][-1]3.编辑距离
思路：
1. 定义状态
设 dp[i][j] 表示将 word1 的前 i 个字符（word1[:i]）转换成 word2 的前 j 个字符（word2[:j]）所需的最少操作数。
2. 初始化
dp[i][0] = i：word2为空，只能删除i次dp[0][j] = j：word1为空，只能插入j次
3. 状态转移公式
比较 word1[i-1] 和 word2[j-1]：
如果相等：
dp[i][j]=dp[i−1][j−1]dp[i][j] = dp[i-1][j-1]dp[i][j]=dp[i−1][j−1]如果不相等：三种操作取最小值：
删除（来自上方）：
dp[i-1][j] + 1插入（来自左方）：
dp[i][j-1] + 1替换（来自左上）：
dp[i-1][j-1] + 1
4. 最终答案
dp[m][n] 即将 word1 转换为 word2 所需的最少操作数，其中 m = len(word1), n = len(word2)。
class Solution:
def minDistance(self, word1: str, word2: str) -> int:
#dp[i][j] 表示以下标i-1结尾的word1转换为以下标j-1结尾的word2所使用的最少操作数是dp[i][j]
#初始化
m, n = len(word1), len(word2)
dp = [[0]*(n+1) for _ in range(m+1)]
for i in range(m+1):
dp[i][0] = i
for j in range(1, n+1):
dp[0][j] = j
for i in range(1, m+1):
for j in range(1, n+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-1]+1, dp[i][j-1]+1) #删除，替换，插入
return dp[-1][-1]动态规划之编辑距离总结篇
判断子序列
- if (s[i - 1] == t[j - 1])
- t中找到了一个字符在s中也出现了
- if (s[i - 1] != t[j - 1])
- 相当于t要删除元素，继续匹配
if (s[i - 1] == t[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1;
else dp[i][j] = dp[i][j - 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];
}两个字符串的删除操作
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] + 2, dp[i - 1][j] + 1, dp[i][j - 1] + 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]}) + 1;
}