学习资料：https://programmercarl.com/0115.不同的子序列.html#算法公开课
动态规划系列之编辑距离问题
学习记录：
115.不同的子序列（当遇到相同字母时，可以选择也可以不选；刚开始没看懂；dp[i][j]是对应i-1结尾和j-1结尾，这样的目的是方便第一行和第一列初始化）
点击查看代码
class Solution(object):
def numDistinct(self, s, t):
"""
:type s: str
:type t: str
:rtype: int
"""
# 动态规划解法
# dp[i][j]表示以j-1为结尾的t片段和以i-1为结尾的s片段，前者作为后者的子序列的情况数量
dp = [[0]*(len(t)+1) for _ in range(len(s)+1)]
# 初始化 dp[i][0], dp[0][j], dp[0][0]
for i in range(len(s)):
dp[i][0] = 1 # j-1=-1,那此时t片段是空字符串，这个就是t片段的子序列
# 特别的，这里设定了，dp[0][0] = 1，下面要避开
for j in range(1, len(t)+1):
dp[0][j] = 0 # i-1 =-1，那此时t片段不为空，而s片段是空字符串，那肯定不是后者的子序列
# 开始遍历
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[-1][-1]
583.两个字符串的删除操作（遇到不同字母就要删除，可以从左上角也可以从左边或者上边执行删除操作；解法二：找公共子序列，根据两字符串长度和公共子序列长度，计算最少操作数）
点击查看代码
class Solution(object):
def minDistance(self, word1, word2):
"""
:type word1: str
:type word2: str
:rtype: int
"""
# 解法一：当word1的某个字符和word2某个字符不同时，可以删除其中一个；最终删除个数就是最小步数
# 动态规划，dp[i][j]代表要使得word1的前i-1和word2的前j-1相同，要删除的最小步数
# 构造二维dp数组
dp = [[0]*(len(word2)+1) for _ in range(len(word1)+1)]
# 初始化
for i in range(len(word1)+1):
dp[i][0] = i # 相当于要一个i-1为结尾的word1片段与空字符串一样，那就得删除从0到i-1就是i个数
for j in range(len(word2)+1):
dp[0][j] = j
# 开始遍历
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:
# 不同，就要删除一次；比如i-1,j-1的可以从左边i,j-1删除i-1这个元素
dp[i][j] = min(dp[i-1][j]+1, dp[i][j-1]+1, dp[i-1][j-1]+2)
return dp[-1][-1]
# 解法二：找到word1和word2的公共子序列，最小步数=len(word1)+len(word2)-len(公共子序列) # 好像是？
# （略）
72.编辑距离（当两字母一样，则操作上等于左上角；若两字母不同，可能执行插入、删除或者替换，这几个就是在左上角或者左边或者上边的基础上加一）
点击查看代码
class Solution(object):
def minDistance(self, word1, word2):
"""
:type word1: str
:type word2: str
:rtype: int
"""
# 用简单例子来说明插入、删除和替换
# eg1. ab和a，可以前者删除b，也可以后者添加a
# eg2. ab和ac，就用替换，两者中任意一个替换最后一个字母
# 动态规划二维dp数组,dp[i][j]代表word1的前i-1段和word2的前j-1段要达到相同需要的最小操作数
# 构造dp数组
dp = [[0]*(len(word2)+1) for _ in range(len(word1)+1)]
# 初始化dp数组的第一行第一列
for i in range(len(word1)+1):
dp[i][0] = i # word1的前i-1段删除所有字母将等于后者空字符串
for j in range(1, len(word2)+1):
dp[0][j] = j
# 开始遍历
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, dp[i][j-1]+1, dp[i-1][j-1]+1)
return dp[-1][-1]
PS:循序渐进，能一点一点理解了，卡尔这排序牛啊
今天阴转多云，开心，吃了大盘鸡、醉鸡、干锅蛙，今天太丰盛了，家里柚子又长虫眼可惜咯