动态规划课堂5-----子序列问题（动态规划 + 哈希表）_子序列:是由数组派生而来的序列,删除(或不删除)数组中的元素而不改变其余元素的顺
目录
引言：
例题2：最长定差子序列
例题3：最长的斐波那契子序列的长度
例题4：最长等差数列
例题5：等差数列划分II-子序列
结语：
引言：
要想解决子序列问题那么就要理解子序列和子数组的区别，二者的定义如下。
子序列：是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7]是数组[0,3,1,6,2,2,7]的子序列。
子数组：是数组中的一个连续部分[6,2,2,7]是数组[0,3,1,6,2,2,7]的子数组。
本节和之前的分析思路一样还是考虑好1. 状态表示，2.状态转移方程，3.初始化，4.填表顺序，5.返回值。希望友友们看完本章后，自己理解一下子数组问题和子序列问题的差别。
例题1：最长递增子序列
链接：最长递增子序列
题目简介：
给你一个整数数组nums，找到其中最长严格递增子序列的长度。
子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7]是数组[0,3,1,6,2,2,7]的子序列。
解法（动态规划）：
1. 状态表示：
这里和子数组的表示方法倒是差不多。
dp[i] 表示：以i 位置元素为结尾的所有⼦序列中，最长递增子序列的长度。
2.状态转移方程：
推状态转移方程时可以画图帮助我们理解，下面这些情况可以大致分为两种，一种就只有一个i还有一种i会跟在i - 1，2，3的某一个后面（子序列）。
对于dp[i] ，我们可以根据子序列的构成⽅式，进⾏分类讨论：
（1）子序列长度为1 ：只能自己玩了，此时dp[i] = 1 。
（2）子序列长度大于1 ： nums[i] 可以跟在前面任何⼀个数后面形成子序列。设前面的某⼀个数的下标为j ，其中0 。只要nums[j] < nums[i] ， i 位置元素跟在j 元素后⾯就可以形成递增序列，长度为dp[j] + 1 。因此，我们仅需找到满足要求的最大的dp[j] + 1 即可。
综上， dp[i] = max(dp[j] + 1, dp[i]) ，其中0 <= j <= i - 1 && nums[j] < nums[i]。
3.初始化：
在求长度之类的dp问题一般可以直接把dp表都初始化成1，因为在我们的状态表示中长度至少为1.因此可以将dp 表内所有元素初始化为1 。
4.填表顺序：
从左往右
5.返回值：
由于不知道最长递增子序列以谁结尾，因此返回dp 表里面的最大值。
代码如下：
class Solution { public int lengthOfLIS(int[] nums) { //1.创建 dp 表 //2.初始化 //3.填表 //4.返回值 int n = nums.length; int[] dp = new int[n]; for(int i = 0;i < n;i++){ dp[i] = 1; } int max = dp[0]; for(int i = 1;i = 0;j--){ if(nums[i] > nums[j]){ dp[i] = Math.max(dp[i],dp[j] + 1); } } max = Math.max(max,dp[i]); } return max; }}时间复杂度：O（n^2）
空间复杂度：O（n）
接下来几题会用到动态规划 + 哈希表
例题2：最长定差子序列
链接：最长定差子序列
题目简介：
给你一个整数数组arr和一个整数difference，请你找出并返回arr中最长等差子序列的长度，该子序列中相邻元素之间的差等于difference。
<
