115.不同的子序列
https://leetcode.cn/problems/distinct-subsequences/description/
代码随想录
https://programmercarl.com/0115.不同的子序列.html#算法公开课
https://leetcode.cn/problems/delete-operation-for-two-strings/description/
https://programmercarl.com/0583.两个字符串的删除操作.html
https://leetcode.cn/problems/edit-distance/description/
https://programmercarl.com/0072.编辑距离.html
115.不同的子序列
- dp[i][j]的含义：第i-1字符串中j-1字符串出现的个数；
- 初始化：考虑dp[i][0]的情况：出现空字符串的个数都为1；dp[0][j]的情况：肯定都是0；
- 递推：
- s[i-1]==t[j-1]相等时；
- 情况1：dp[i-1][j-1]加上这个元素的字符串个数：就差这个元素的个数：ba
- 情况2：dp[i-1][j]:比现在少的字符串中就包含了j的字符串的个数：之前包含的bag的个数
- 例如：babagg=>babag中含有的bag的个数+babag中含有ba的个数=总共的个数；
- s[i-1]!=t[j-1]时
- 只有之前所包含的字符串的个数；
- s[i-1]==t[j-1]相等时；
点击查看代码
```python class Solution: def numDistinct(self, s: str, t: str) -> int: m = len(s)
n = len(t)
## 定义dp
dp = [[0] *(n+1) for _ in range(m+1)]
##初始化
for i in range(m+1):
dp[i][0] = 1
##遍历
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]
</details>
# 583. 两个字符串的删除操作
## 题解
### 思路一：直接记录需要删除元素的个数；
- dp[i][j]的含义：i-1结尾和j-1的字符串需要删除的字符的个数；
- 初始化：
- dp[0][j] = j 和空字符串比需要删的就是自身的个数；
- dp[i][0] = i
- 递推
- 字符串相同时：不需要做删除操作
- dp[i][j] = dp[i-1][j-1]
- 字符串不同时：考虑三种情况：dp[i][j] = min(dp[i-1][j]+1,dp[i][j-1]+1)
- 斜对角：删除2个元素；（可以合并）
- 删除s
- 删除t
<details>
<summary>点击查看代码</summary>
```python
class Solution:
def minDistance(self, word1: str, word2: str) -> int:
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(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][j-1]+1)
return dp[-1][-1]
思路二：计算相同元素，删除不同即可
- dp[i][j]的含义：i-1结尾和j-1的字符串相同字符串的个数
- dp[i][j]全部为0
- 递推：
- 字符串相同时
-dp[i][j] =dp[i-1][j-1]+1 - 字符串不同时:找包含最多的字符串
-dp[i][j]= max(dp[i-1][j],dp[i][j-1])
- 字符串相同时
点击查看代码
class Solution:
def minDistance(self, word1: str, word2: str) -> int:
m = len(word1)
n = len(word2)
dp = [[0]*(n+1) for _ in range(m+1)]
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]+1
else:
dp[i][j] = max(dp[i-1][j],dp[i][j-1])
res = m+n-2*dp[-1][-1]
return res
72. 编辑距离
题解
- dp[i][j]含义：i-1结尾的word1 转换成 j-1结尾的word2 所使用的最少操作数
- 初始化：dp[i][0] = i dp[0][j] =j 全部都是删除
- 递推
- 字符串相同时：
-不需要有操作：dp[i][j] = dp[i-1][j-1] - 字符串不同时：
- 删除增加：word1删除:dp[i-1][j]+1 word2删除：dp[i][j-1]+1
- 替换：word1[i-1]换成wor2[j-1]:dp[i-1][j-1]+1
- 字符串相同时：
点击查看代码
import numpy as np
class Solution:
def minDistance(self, word1: str, word2: str) -> int:
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(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]+1,dp[i-1][j]+1,dp[i][j-1]+1)
return dp[-1][-1]
总结编辑距离篇
- 做题方法：自己将dp矩阵写出来 尝试自己按照含义找一下；在找的过程中总结状态转移方程；
- 不要找规律，记不住的；