代码随想录算法训练营 Day 38
Published:
动态规划五部曲
- 确定dp数组以及下标的含义
- 确定递推公式
- 初始化dp数组
- 确定遍历顺序
- 举例推导dp数组
第5步随着输入不同而变化，因此在此省去
Q1. LeetCode 1143
与LeetCode 718类似，但这里不再要求连续，只是要求相对顺序一致，所以对于初始化和状态转换都有影响
前四步：
- 使用二维的dp数组，dp[i][j]表示text1[:i+1]和text2[:j+1]之间的最长公共子序列的长度
- 递推公式：1. 两个字符相同，$dp[i][j] = dp[i - 1][j - 1] + 1$；2. 两个字符不同，本题依然要更新长度，因此 $dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])$
- 初始化：整体初始化为0，然后更新第一行和第一列，只要能找到两个位置相同，那么除了当前位置要修改，之后的所有位置都需要设置成1（有一个长度为1的子序列）
- 遍历顺序：两层循环均从前向后遍历
class Solution:
def longestCommonSubsequence(self, text1: str, text2: str) -> int:
n1 = len(text1)
n2 = len(text2)
dp = [[0] * n1 for _ in range(n2)]
for i in range(n2):
if text1[0] == text2[i]:
dp[i][0] = 1
else:
if i > 0:
dp[i][0] = dp[i - 1][0]
for j in range(n1):
if text2[0] == text1[j]:
dp[0][j] = 1
else:
if j > 0:
dp[0][j] = dp[0][j - 1]
for i in range(1, n2):
for j in range(1, n1):
if text2[i] == text1[j]:
dp[i][j] = dp[i - 1][j - 1] + 1
else:
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
return dp[-1][-1]
复杂度分析
时间复杂度：O($n \times m$) 空间复杂度：O($n \times m$)
Q2. LeetCode 1035
可以看到不相交的连线数，就是要找到一个相对顺序一致的最长子序列。因为如果顺序交错的话，线段一定会相交。那么和Q1相同
class Solution:
def maxUncrossedLines(self, nums1: List[int], nums2: List[int]) -> int:
n1 = len(nums1)
n2 = len(nums2)
dp = [[0] * n1 for _ in range(n2)]
for i in range(n2):
if nums1[0] == nums2[i]:
dp[i][0] = 1
else:
if i > 0:
dp[i][0] = dp[i - 1][0]
for j in range(n1):
if nums2[0] == nums1[j]:
dp[0][j] = 1
else:
if j > 0:
dp[0][j] = dp[0][j - 1]
for i in range(1, n2):
for j in range(1, n1):
if nums2[i] == nums1[j]:
dp[i][j] = dp[i - 1][j - 1] + 1
else:
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
return dp[-1][-1]
复杂度分析
时间复杂度：O($n \times m$) 空间复杂度：O($n \times m$)
Q3. LeetCode 53
本题也可使用贪心算法
前四步：
- 使用一维的dp数组，dp[i]表示以nums[i]结尾的连续子数组的最大和
- 递推公式：因为是连续的子数组，所以就是两种情况：1. 将其和之前的子数组结合在一起；2. 以当前位置作为子数组的起始位置。$dp[i] = max(dp[i - 1] + nums[i], nums[i])$
- 初始化：整体初始化为0，第一个数字只能由自己构成子数组，因此 $dp[0]=nums[0]$
- 遍历顺序：从前向后遍历（从1开始）
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
n = len(nums)
dp = [0] * n
dp[0] = nums[0]
for i in range(1, n):
dp[i] = max(dp[i - 1] + nums[i], nums[i])
return max(dp)
复杂度分析
时间复杂度：O($n$) 空间复杂度：O($n$)
Q4. LeetCode 392
与Q1类似，但本题是要在一个字符串中匹配另一个字符串，所以只会有原字符串删除元素的情况（初始化和状态转换可以省去一部分）
class Solution:
def isSubsequence(self, s: str, t: str) -> bool:
n1 = len(s)
n2 = len(t)
if n1 == 0:
return True
if n2 == 0 and n1 != 0:
return False
dp = [[0] * n1 for _ in range(n2)]
for i in range(n2):
if s[0] == t[i]:
dp[i][0] = 1
else:
if i > 0:
dp[i][0] = dp[i - 1][0]
for i in range(1, n2):
for j in range(1, n1):
if t[i] == s[j]:
dp[i][j] = dp[i - 1][j - 1] + 1
else:
dp[i][j] = dp[i - 1][j]
return dp[-1][-1] == n1
复杂度分析
时间复杂度：O($n \times m$) 空间复杂度：O($n \times m$)
本题也可以用双指针法，两个指针分别在两个字符串上
class Solution:
def isSubsequence(self, s: str, t: str) -> bool:
n1 = len(s)
n2 = len(t)
s_idx = 0
t_idx = 0
while t_idx < n2 and s_idx < n1:
if s[s_idx] == t[t_idx]:
s_idx += 1
t_idx += 1
if s_idx == n1:
return True
return False
复杂度分析
时间复杂度：O($n$) 空间复杂度：O(1)