序列dp常见思路总结

• 序列dp是常考的题型，那么我们我们可以根据什么将它们分类，然后对于不同的类型的题目使用对应的模版进行求解？
• 首先，子序列不同于子数组，子数组是要求元素在原来的序列当中是连续的，而子序列的元素不要求在原来的序列当中是连续的
• 总的来说，子序列dp问题主要是两种套路

选或不选

• 当面对是 子序列+相邻元素无关，也就说当面对当前的元素nums[i]的时候，并没有相邻元素之间的限制的条件，也就是都可以选，所以可以采用的是 选或不选的策略
• 常常使用0-1背包问题模版进行求解

枚举哪一个

• 当面对子序列+相邻元素相关，也就是对于原来的元素，我们在选择的时候，存在限制条件，那么我们就需要考虑枚举哪一个
• 当然，代表问题当然是最长递增子序列，在定义的时候，我们常常需要定义dp[i]为以nums[i]结尾的情况的最值或者方案数

习题

选或不选

494.目标和

494.目标和

• 思路分析：由于选择的元素，在原来的序列当中，并没有限制条件，所以我们就直接使用选或不选，在这题当中，我们通过转化，可以求解正的数或者负的数的和为目标值的问题，考虑使用0-1背包的模版进行求解

class Solution:def findTargetSumWays(self, nums: List[int], target: int) -> int:# 子序列问题，相邻元素之间并没有过多的要求# 根据式子，我们只需找出正数的和为 (sum(nums) + target)//2n = len(nums)p = sum(nums) + target # 这里我们求解正的数和为tarif p < 0 or p % 2 == 1:return 0 tar = p // 2 # 这个就可以转化为0-1背包问题# dp[i][j]表示前i个物体中，选中为j的方案数dp = [[0]*(tar+1) for _ in range(n+1)]dp[0][0] = 1 for i in range(n):for j in range(tar+1):if j < nums[i]:dp[i+1][j] = dp[i][j]else:dp[i+1][j] = dp[i][j] + dp[i][j-nums[i]]return dp[n][tar]

枚举哪一个

300.最长递增子序列

300.最长递增子序列

• 思路分析：最长递增子序列模版题目，首先为了更好理解这个枚举哪一个，我们使用o(n^2)的时间复杂度的进行求解,当然后面也可以使用线段树进行优化为o(nlogn)的复杂度

class Solution:def lengthOfLIS(self, nums: List[int]) -> int:# 首先最简单的情况，当然是考虑o(n^2)的时间复杂度的算法n = len(nums)# 定义dp[i]为以nums[i]结尾的最大递增子序列的长度dp = [1]*n # dp[i] = max(dp[j]) + 1,并且 nums[i] > nums[j] , j < i for i in range(1,n):for j in range(i):if nums[i] > nums[j] and dp[i] < dp[j] + 1:dp[i] = dp[j] + 1return max(dp)