代码随想录算法训练营 Day 39
Published:
动态规划五部曲
- 确定dp数组以及下标的含义
- 确定递推公式
- 初始化dp数组
- 确定遍历顺序
- 举例推导dp数组
第5步随着输入不同而变化，因此在此省去
Q1. LeetCode 115
与LeetCode 718类似，但这里不再要求连续，只是要求相对顺序一致，所以对于初始化和状态转换都有影响
前四步：
- 使用二维的dp数组，dp[i][j]表示以t[j]为结尾的模式子字符串在以s[i]为结尾的原字符子串中出现的次数
- 递推公式：1. 两个字符t[j]和s[i]不相同，$dp[i][j] = dp[i - 1][j]$（跟上一位进行匹配的个数一致）；2. 两个字符相同，存在两种情况：1）该字符是重复字符，即s[i] = s[i - 1]，那么需要匹配次数就是 $dp[i][j] = dp[i - 1][j]$；2）该字符为新的字符，$dp[i][j] = dp[i - 1][j - 1]$。所以递归公式为$dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]$
- 初始化：整体初始化为0，然后更新第一列，判断s[i]和t[0]是否相等，如果相等就在前一个基础上加1
- 遍历顺序：两层循环均从前向后遍历
class Solution:
def numDistinct(self, s: str, t: str) -> int:
n1 = len(s)
n2 = len(t)
if n2 > n1:
return 0
dp = [[0] * n2 for _ in range(n1)]
for i in range(n1):
if i == 0 and s[i] == t[0]:
dp[i][0] = 1
if i > 0:
if s[i] == t[0]:
dp[i][0] = dp[i - 1][0] + 1
else:
dp[i][0] = dp[i - 1][0]
for i in range(1, n1):
for j in range(1, n2):
if s[i] == t[j]:
dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]
else:
dp[i][j] = dp[i - 1][j]
return dp[-1][-1]
复杂度分析
时间复杂度：O($n \times m$) 空间复杂度：O($n \times m$)
Q2. LeetCode 583
将其转化为找到两者的最长公共子序列，然后要删除的元素就是两个字符串长度减去二倍的最长公共子序列长度
class Solution:
def minDistance(self, word1: str, word2: str) -> int:
n = len(word1)
m = len(word2)
dp = [[0] * n for _ in range(m)]
flag = 0
for i in range(m):
if word1[0] == word2[i]:
dp[i][0] = 1
flag = 1
elif flag:
dp[i][0] = 1
flag = 0
for j in range(n):
if word1[j] == word2[0]:
dp[0][j] = 1
flag = 1
elif flag:
dp[0][j] = 1
for i in range(1, m):
for j in range(1, n):
if word2[i] == word1[j]:
dp[i][j] = dp[i - 1][j - 1] + 1
else:
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
return n + m - 2 * dp[-1][-1]
复杂度分析
时间复杂度：O($n \times m$) 空间复杂度：O($n \times m$)
Q3. LeetCode 72
前四步：
- 使用二维的dp数组，dp[i][j]表示word1[:i]和word2[:j]最少需要的操作次数使得两者相同
- 递推公式：1. word1[i - 1]和word2[j - 1]相同，那么 $dp[i][j] = dp[i - 1][j - 1]$（不需要额外的操作）；2. 两者不同，word1删除一位，$dp[i][j]=dp[i-1][j] + 1$；word1插入一位，$dp[i][j] = dp[i][j - 1] + 1$；word1替换一位，$dp[i][j]=dp[i-1][j-1]+1$。最后三者取最小值即可
- 初始化：整体初始化为0。然后初始化第一行和第一列，word1[:0]或word2[:0]都代表空字符串，要让另一个和其一样，因此只能删除所有出现的字符
- 遍历顺序：从前向后遍历（从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(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 - 1][j], dp[i][j - 1]) + 1
return dp[-1][-1]
复杂度分析
时间复杂度：O($n \times m$) 空间复杂度：O($n \times m$)
总结
可以看出将状态数组看作是A[:i]/B[:j]会比A[:i+1]/B[:j+1]方便很多