动态规划 - 编辑距离

115. 不同的子序列

困难

给你两个字符串 s 和 t ，统计并返回在 s 的 子序列 中 t 出现的个数，结果需要对 10^9 + 7 取模。

算法思想：利用动态规划，分s[i - 1] 与 t[j - 1]相等，s[i - 1] 与 t[j - 1] 不相等两种情况具体讨论如何匹配。

1、dp数组及其下标含义：dp[i][j] 以i-1为结尾的字符串s中包含以j-1为结尾的字符串t

的个数。

2、递推公式：

• s[i - 1] 与 t[j - 1]相等: dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]
• s[i - 1] 与 t[j - 1] 不相等: dp[i][j] = dp[i - 1][j]

如果s[i-1] == t[j-1]，dp[i][j]可以有两部分组成。

一部分是用s[i - 1]来匹配，那么个数为dp[i - 1][j - 1]。

一部分是不用s[i - 1]来匹配，个数为dp[i - 1][j]。

例如： s：bagg 和 t：bag ，s[3] 和 t[2]是相同的，但是字符串s也可以不用s[3]来匹配.

如果s[i-1] != t[i-1]，那么不能用s[i-1]来匹配（模拟在s中删除这个元素），dp[i][j] = dp[i-1][j]

3、初始化

dp[0][0] = 1, dp[i][0] = 1（s匹配空字符串，删除到为空这一种方法）,dp[0][j] = 0（）

4、遍历

从前到后，从上到下

class Solution:def numDistinct(self, s: str, t: str) -> int:dp = [[0] * (len(t)+1) for _ in range(len(s)+1)]for i in range(len(s)):dp[i][0] = 1for j in range(1, len(t)):dp[0][j] = 0for 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] #用s[i - 1]来匹配和不用else:dp[i][j] = dp[i-1][j]# 不能用s[i-1]来匹配（模拟在s中删除这个元素）return dp[-1][-1]

583. 两个字符串的删除操作

中等

给定两个单词 word1 和 word2 ，返回使得 word1 和  word2 相同所需的最小步数。

每步 可以删除任意一个字符串中的一个字符。

直接删 

算法思想：利用动态规划，如果word1[i-1] == word2[j-1]相等，那么不需要删除操作，如果不相等，那么可以删word1、word2或者都删，取最小值。

1、dp数组及其下标含义：dp[i][j] 以i-1为结尾的字符串word1和以j-1为结尾的字符串word2

最少需要删除几次可以相等。

2、递推公式：

• s[i - 1] 与 t[j - 1]相等: dp[i][j] = dp[i - 1][j - 1]
• s[i - 1] 与 t[j - 1] 不相等: dp[i][j] = min(dp[i-1][j]+1, dp[i][j-1]+1,dp[i-1][j-1]+2)

如果s[i-1] == t[j-1]，不需要删。dp[i][j] = dp[i - 1][j - 1]

如果s[i-1] != t[i-1]，有三种删除方式，删word1/word2/都删，取最小值

3、初始化

dp[0][0] = 1, dp[i][0] = i；dp[0][j] = j

4、遍历

从前到后，从上到下

class Solution:def minDistance(self, word1: str, word2: str) -> int:dp = [[0] * (len(word2)+1) for _ in range(len(word1)+1)]for i in range(len(word1)+1):dp[i][0] = ifor j in range(1, len(word2)+1):dp[0][j] = jfor 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: # 不相等，可以删word1\word2\都删 dp[i][j] = min(dp[i-1][j]+1, dp[i][j-1]+1,dp[i-1][j-1]+2)return dp[-1][-1]

求最长公共子序列

class Solution(object):def minDistance(self, word1, word2):m, n = len(word1), len(word2)# dp 求解两字符串最长公共子序列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] + 1else:dp[i][j] = max(dp[i-1][j], dp[i][j-1])# 删去最长公共子序列以外元素return m + n - 2 * dp[-1][-1]

72. 编辑距离 

中等

给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数  。

你可以对一个单词进行如下三种操作：

• 插入一个字符
• 删除一个字符
• 替换一个字符

1、dp数组及其下标含义：dp[i][j] 以i-1为结尾的字符串word1和以j-1为结尾的字符串word2

最少需要操作几次可以相等。

2、递推公式：

• s[i - 1] 与 t[j - 1]相等: dp[i][j] = dp[i - 1][j - 1]
• s[i - 1] 与 t[j - 1] 不相等: dp[i][j] = min(dp[i-1][j]+1, dp[i][j-1]+1,dp[i-1][j-1]+1)

如果s[i-1] == t[j-1]，不需要操作。dp[i][j] = dp[i - 1][j - 1]

如果s[i-1] != t[i-1]，可以插入、删除、替换

•         删除：删word1: dp[i][j] = dp[i - 1][j] +1；删word2: dp[i][j] = dp[i][j-1] +1
•         插入：相当于删除
•         替换：只需一次操作，dp[i][j] = dp[i - 1][j - 1] + 1

3、初始化

dp[0][0] = 1, dp[i][0] = i；dp[0][j] = j

4、遍历

从前到后，从上到下

class Solution:def minDistance(self, word1: str, word2: str) -> int:dp = [[0] * (len(word2)+1) for _ in range(len(word1)+1)]for i in range(len(word1)+1):dp[i][0] = ifor j in range(len(word2)+1):dp[0][j] = jfor 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-1][j], dp[i][j-1]) + 1return dp[-1][-1]