代码随想录算法训练营 Day 37
Published:
动态规划五部曲
- 确定dp数组以及下标的含义
- 确定递推公式
- 初始化dp数组
- 确定遍历顺序
- 举例推导dp数组
第5步随着输入不同而变化，因此在此省去
Q1. LeetCode 300
前四步：
- 使用一维的dp数组，dp[i]表示以第i位数字结尾的最长递增子序列长度
- 递推公式：比较某个数字和前面的数字，如果比前面数字大，那么序列长度加1。因此需要两层循环，找到当前位置的最大值，即 $dp[i]=max(dp[i], dp[j] + 1)$
- 初始化：整体初始化为1，因为数字本身就是一个长度为1的序列
- 遍历顺序：两层循环均从前向后遍历
class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
n = len(nums)
dp = [1] * n
for i in range(1, n):
for j in range(i):
if nums[i] > nums[j]:
dp[i] = max(dp[i], dp[j] + 1)
return max(dp)
复杂度分析
时间复杂度：O($n^2$) 空间复杂度：O($n$)
Q2. LeetCode 674
和Q1类似，但因为现在要找的连续子数组，因此只需要比较当前位置和前一位置的大小
class Solution:
def findLengthOfLCIS(self, nums: List[int]) -> int:
n = len(nums)
dp = [1] * n
for i in range(1, n):
if nums[i] > nums[i - 1]:
dp[i] = dp[i - 1]+ 1
return max(dp)
复杂度分析
时间复杂度：O($n$) 空间复杂度：O($n$)
Q3. LeetCode 718
前四步：
- 使用二维的dp数组，dp[i][j]表示nums1[:i+1]和nums2[:j+1]之间的最长重复数组的长度
- 递推公式：假如两个数组中存在 $nums1[i]$和 $nums2[j]$相同的情况，那么最长重复数组的长度可以表示为 $dp[i - 1][j - 1] + 1$
- 初始化：整体初始化为0，然后初始化第一行和第一列
- 遍历顺序：两层循环均从前向后遍历（从1开始）
class Solution:
def findLength(self, nums1: List[int], nums2: List[int]) -> int:
m, n = len(nums1), len(nums2)
dp = [[0] * n for _ in range(m)]
for i in range(m):
if nums1[i] == nums2[0]:
dp[i][0] = 1
for j in range(n):
if nums2[j] == nums1[0]:
dp[0][j] = 1
for i in range(1, m):
for j in range(1, n):
if nums1[i] == nums2[j]:
dp[i][j] = dp[i - 1][j - 1] + 1
return max(map(max, dp))
复杂度分析
时间复杂度：O($m \times n$) 空间复杂度：O($m \times n$)