子序列问题
- 最长递增自序列
- 摆动序列
- 最长递增子序列的个数
- 最长数对链
- 最长定差子序列
- 最长的斐波那契子序列的长度
- 最长等差数列
- 等差数列划分||-子序列
最长递增自序列
动态规划
状态表示：
dp[i]：以i位置结尾，所有自序列中，最长长度
状态转移方程：
长度为1 1
长度大于1 j取值范围 [0,i-1]，求出 j 结尾中的最长子序列长度+1就是dp[i]的结果
初始化：
此时最小长度为1，此时可以将dp表初始化为1，不用考虑长度为1的情况
填表顺序：从左到右
返回值：dp表中最大值
classSolution{publicintlengthOfLIS(int[]nums){intn=nums.length;int[]dp=newint[n];for(inti=0;i<n;i++){dp[i]=1;//最小为1}intret=1;for(inti=0;i<n;i++){for(intj=0;j<i;j++){if(nums[i]>nums[j]){dp[i]=Math.max(dp[i],dp[j]+1);}}//更新结果ret=Math.max(ret,dp[i]);}returnret;}}摆动序列
题目解析：求最长摆动序列长度，就是两个元素差值是一正一负情况，也就是递增和递减先后出现
状态表示：
f[i] : 以i位置结尾元素子序列中，最后呈现"上升"趋势最长摆动序列长度
g[i] : 以i位置结尾元素子序列中，最后呈现"下降"趋势最长摆动序列长度
状态转移方程：
长度为1 1
长度大于1 j取值范围 [0,i-1] ，求出满足摆动序列最大长度
nums[j] < nums[i] -> f[i] = max(f[i] , g[j] + 1)
nums[j] > nums[i] -> g[i] = max(g[i] , f[j] + 1)
初始化：
此时最小长度为1，此时可以将f和g表初始化为1，不用考虑长度为1的情况
填表顺序：从左到右
返回值：f和g表中最大值
classSolution{publicintwiggleMaxLength(int[]nums){intn=nums.length;int[]f=newint[n];//结尾是上升int[]g=newint[n];//结尾是下降for(inti=0;i<n;i++){f[i]=g[i]=1;}intret=1;for(inti=1;i<n;i++){for(intj=0;j<i;j++){if(nums[j]<nums[i]){f[i]=Math.max(f[i],g[j]+1);}elseif(nums[j]>nums[i]){g[i]=Math.max(g[i],f[j]+1);}}ret=Math.max(Math.max(f[i],g[i]),ret);}returnret;}}最长递增子序列的个数
题目解析：找出最长递增子序列的个数，上面已经知道如何找最长子序列了
状态表示：
len[i] : 以i位置结尾元素子序列中，最长递增子序列的"长度"
count[i] : 以i位置结尾元素子序列中，最长递增子序列的"个数"
状态转移方程：
长度为1 1
长度大于1 j取值范围 [0,i-1] ，nums[i] > nums[j] 找出最长递增子序列长度及其个数
if(len[j]+1 == len[i]){
//更新最大长度的值
count[i] += count[j];
//最长长度发生变化
}else if(len[j] + 1 > len[i]){
len[i] = len[j]+1;
count[i] = count[j];//重新计数
}
初始化：
最长递增子序列长度为1，出现此时最长递增子序列个数最小为1，
填表顺序：从左到右
返回值：需要找出len表中最大长度，并找出最大长度出现次数count表、
classSolution{publicintfindNumberOfLIS(int[]nums){intn=nums.length;int[]len=newint[n];//最长递增子序列长度int[]count=newint[n];//最长递增子序列出现的个数for(inti=0;i<n;i++){len[i]=count[i]=1;}intretlen=1;intretcount=1;for(inti=1;i<n;i++){for(intj=0;j<i;j++){if(nums[j]<nums[i]){//长度一样if(len[j]+1==len[i]){//更新最大长度的值count[i]+=count[j];//最长长度发生变化}elseif(len[j]+1>len[i]){len[i]=len[j]+1;count[i]=count[j];//重新计数}}}if(retlen==len[i]){retcount+=count[i];}elseif(retlen<len[i]){//跟新最长长度，重新计数retlen=len[i];retcount=count[i];}}returnretcount;}}最长数对链
题目解析：最长数对链长度，当一个数对的头大于一个数对的尾，可以将其跟随到尾部，此时这里是任意选择
因为这里任意选择，导致填表需要根据其前后两端进行填表，无法确定，此时可以先根据其数对中第一个元素进行从小到大排序，这样只需要根据当前位置之前的值进行填表即可，其排序后，其前面元素是无法插在当前数对的尾部
动态规划(先排序)
状态表示：
dp[i]：以i位置元素结尾， 最长数对链路长度
状态转移方程：
长度为1 1
长度大于1 j取值范围 [0,i-1]，求出 j 结尾中的dp[j]+1最大值就是dp[i]的结果
初始化：
此时最小长度为1，此时可以将dp表初始化为1，不用考虑长度为1的情况
填表顺序：从左到右
返回值：dp表中最大值
classSolution{publicintfindLongestChain(int[][]pairs){intn=pairs.length;//根据数对中第一个元素进行排序，这样每次只根据前面更新dp表即可Arrays.sort(pairs,(a,b)->a[0]-b[0]);int[]dp=newint[n];for(inti=0;i<n;i++){dp[i]=1;}intret=1;for(inti=1;i<n;i++){for(intj=0;j<i;j++){//尾 < 头if(pairs[j][1]<pairs[i][0]){dp[i]=Math.max(dp[i],dp[j]+1);}}ret=Math.max(ret,dp[i]);}returnret;}}最长定差子序列
题目解析：找出最长定差子序列长度
动态规划
状态表示：
dp[i]：以i位置元素结尾， 最长定差子序列长度
状态转移方程：
当前元素是a
找是否存在 a - difference,没有就是1
找到可能有多个，但是只需要最后一个即可，因为其长度是最长的
初始化：
此时最小长度为1，此时可以将dp表初始化为1，不用考虑长度为1的情况
填表顺序：从左到右
返回值：dp表中最大值
这里因为其定差是确定的，可以使用哈希表将其arr[i]，和 dp[i]进行绑定 其长度为数组中 其key:arr[i]-difference value：长度+1就是arr[i]对应的值 但是这里可能找不到，找不到，自己构成，长度为1遍历数组，找其arr[i]-difference长度进行更新，数组是从前向后，其到后面结果会覆盖前面，符合最长长度(最后一个是最长)classSolution{publicintlongestSubsequence(int[]arr,intdifference){//使用哈希表，用其做dpMap<Integer,Integer>hash=newHashMap<>();//arr[i] dp[i]intret=1;for(inta:arr){//以arr[i]结尾的定差长度//没有就是1//这里需要最长的，因此最长的是arr数组中最后一个a-difference == b//这里从前向后，相同值会覆盖，所以最终结果就是最长hash.put(a,hash.getOrDefault(a-difference,0)+1);ret=Math.max(ret,hash.get(a));}returnret;}}最长的斐波那契子序列的长度
题目解析：找出最长斐波那契子序列长度，满足斐波那契就是 arr[i] + arr[i+1] == arr[i+2]，一个序列所有元素都满足
动态规划
状态表示：
dp[i][j]：以i位置元素及其j位置元素结尾， 最长斐波那契子序列长度(i < j)
状态转移方程：
a = arr[j] - arr[i]找是否存在这个数
存在元素a a < arr[i] dp[i][j] = dp[k][i] + 1
存在元素a arr[i] <a < arr[j] - > 2
不存在a 2
初始化：
将dp表中都初始化为2，简化状态转移方程填写
填表顺序：从上到下
返回值：dp表中最大值
可以将所有元素及其下标对应关系放到哈希表中，这样查找效率高
classSolution{publicintlenLongestFibSubseq(int[]arr){intn=arr.length;int[][]dp=newint[n][n];//以i,j结尾最长斐波那契子序列长度Map<Integer,Integer>hash=newHashMap<>();//将值和下标绑定//这里是严格递增不会有重复元素for(inti=0;i<n;i++){hash.put(arr[i],i);}for(inti=0;i<n;i++){for(intj=0;j<n;j++){dp[i][j]=2;}}intret=2;for(intj=2;j<n;j++){//固定最后一个数for(inti=1;i<j;i++){//倒数第二个数intx=arr[j]-arr[i];//需要找的值//找到这个数，并且其位置是在i下标之前if(x<arr[i]&&hash.containsKey(x)){dp[i][j]=dp[hash.get(x)][i]+1;ret=Math.max(ret,dp[i][j]);}}}//可能构不成斐波那契子序列returnret<3?0:ret;}}最长等差数列
题目解析：求最长等差子序列长度
动态规划
和上题一样，需要知道不仅需要最后一个数也需要倒数第二个数，依旧使用二维数组
dp[i][j]：以i位置元素及其j位置元素结尾子序列中， 最长等差序列长度(i < j)
状态转移方程：
a = arr[j] - arr[i]找是否存在这个数，有的话假设下标为k
存在元素a k < i dp[i][j] = dp[k][i] + 1
存在元素a i <= k <= j 2
不存在a 2
初始化：
将dp表中都初始化为2，简化状态转移方程填写
填表顺序：
有要求，1.固定倒数第二个数，枚举倒数第一个数，从哈希表中找符合等差的数(为了正确使用哈希表)
返回值：dp表中最大值
使用一个哈希表
一边dp，一边将最近元素<元素,下标>放入哈希表中
当i位置(倒数第二个数)填写之后，将i位置对应元素和下标放入哈希表中
因为i每次固定，所以这里哈希表中存放就是最近的，并且使用不会错
如果是固定最后一个数，枚举倒数第二个数，其i不断变化，离i倒数第二个数最近元素下标不但变化，会导致错误
classSolution{publicintlongestArithSeqLength(int[]nums){intn=nums.length;int[][]dp=newint[n][n];Map<Integer,Integer>hash=newHashMap<>();//初始化for(inti=0;i<n;i++){for(intj=0;j<n;j++){dp[i][j]=2;}}hash.put(nums[0],0);intret=2;for(inti=1;i<n;i++){//先确定倒数第二个数for(intj=i+1;j<n;j++){//枚举最后一个数intx=2*nums[i]-nums[j];//哈希表中找出一个满足等差的数if(hash.containsKey(x)){dp[i][j]=dp[hash.get(x)][i]+1;ret=Math.max(ret,dp[i][j]);}}//将其放入哈希表中hash.put(nums[i],i);}returnret;}}等差数列划分||-子序列
题目解析：求出等差序列的个数
这里不仅要知道等差序列的长度，也要知道等差序列对应的序列，这样后续填表才可以知道是否可以构成等差数列
动态规划
状态表示
dp[i][j]：以i位置元素及其j位置元素结尾子序列中， 等差序列的个数(i < j)
状态转移方程：
a = 2 * arr[i] - arr[j]找出所有符合要求k下标，因为都可以构成等差序列，都要加上
存在元素a 所有的符合要求k下标 k < i dp[i][j] = dp[k][i] + 1
存在元素a 下标不符合要求 0
不存在a 0
初始化：
将dp表中都初始化为0，至少3个元素才可以构成等差序列
填表顺序：
固定倒数第一个数，枚举倒数第二个数，从哈希表中找符合等差的数
返回值：dp表的总和
优化找符合等差序列的数 a
使用哈希表<元素，下标数组>,dp之前，将其元素和下标数组(一个元素可能有多个)对应关系进行绑定
这里的数虽然不会溢出，但是其运算过程中可能会溢出，因此这里哈希表中类型改为long类型
classSolution{publicintnumberOfArithmeticSlices(int[]nums){intn=nums.length;int[][]dp=newint[n][n];int[]pairs=newint[n];//使用long类型，计算过程中可能会溢出Map<Long,List<Integer>>hash=newHashMap<>();//将值和下标数组对应for(inti=0;i<n;i++){longtem=(long)nums[i];if(!hash.containsKey(tem)){hash.put(tem,newArrayList<>());}hash.get(tem).add(i);}intsum=0;for(intj=2;j<n;j++){//倒数第一个数for(inti=1;i<j;i++){//倒数第二个数longx=2L*nums[i]-nums[j];if(hash.containsKey(x)){//所有符合要求的下标for(intk:hash.get(x)){if(k<i){dp[i][j]+=dp[k][i]+1;}else{//下标是递增存储，不符合要求后面也都不符合break;}}sum+=dp[i][j];}}}returnsum;}}
