子序列问题最长递增自序列摆动序列最长递增子序列的个数最长数对链最长定差子序列最长的斐波那契子序列的长度最长等差数列等差数列划分||-子序列最长递增自序列动态规划状态表示dp[i]以i位置结尾所有自序列中最长长度状态转移方程长度为1 1长度大于1 j取值范围 [0,i-1]求出 j 结尾中的最长子序列长度1就是dp[i]的结果初始化此时最小长度为1此时可以将dp表初始化为1不用考虑长度为1的情况填表顺序从左到右返回值dp表中最大值classSolution{publicintlengthOfLIS(int[]nums){intnnums.length;int[]dpnewint[n];for(inti0;in;i){dp[i]1;//最小为1}intret1;for(inti0;in;i){for(intj0;ji;j){if(nums[i]nums[j]){dp[i]Math.max(dp[i],dp[j]1);}}//更新结果retMath.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){intnnums.length;int[]fnewint[n];//结尾是上升int[]gnewint[n];//结尾是下降for(inti0;in;i){f[i]g[i]1;}intret1;for(inti1;in;i){for(intj0;ji;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);}}retMath.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){intnnums.length;int[]lennewint[n];//最长递增子序列长度int[]countnewint[n];//最长递增子序列出现的个数for(inti0;in;i){len[i]count[i]1;}intretlen1;intretcount1;for(inti1;in;i){for(intj0;ji;j){if(nums[j]nums[i]){//长度一样if(len[j]1len[i]){//更新最大长度的值count[i]count[j];//最长长度发生变化}elseif(len[j]1len[i]){len[i]len[j]1;count[i]count[j];//重新计数}}}if(retlenlen[i]){retcountcount[i];}elseif(retlenlen[i]){//跟新最长长度重新计数retlenlen[i];retcountcount[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){intnpairs.length;//根据数对中第一个元素进行排序这样每次只根据前面更新dp表即可Arrays.sort(pairs,(a,b)-a[0]-b[0]);int[]dpnewint[n];for(inti0;in;i){dp[i]1;}intret1;for(inti1;in;i){for(intj0;ji;j){//尾 头if(pairs[j][1]pairs[i][0]){dp[i]Math.max(dp[i],dp[j]1);}}retMath.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){//使用哈希表用其做dpMapInteger,IntegerhashnewHashMap();//arr[i] dp[i]intret1;for(inta:arr){//以arr[i]结尾的定差长度//没有就是1//这里需要最长的因此最长的是arr数组中最后一个a-difference b//这里从前向后相同值会覆盖所以最终结果就是最长hash.put(a,hash.getOrDefault(a-difference,0)1);retMath.max(ret,hash.get(a));}returnret;}}最长的斐波那契子序列的长度题目解析找出最长斐波那契子序列长度满足斐波那契就是 arr[i] arr[i1] arr[i2]一个序列所有元素都满足动态规划状态表示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){intnarr.length;int[][]dpnewint[n][n];//以i,j结尾最长斐波那契子序列长度MapInteger,IntegerhashnewHashMap();//将值和下标绑定//这里是严格递增不会有重复元素for(inti0;in;i){hash.put(arr[i],i);}for(inti0;in;i){for(intj0;jn;j){dp[i][j]2;}}intret2;for(intj2;jn;j){//固定最后一个数for(inti1;ij;i){//倒数第二个数intxarr[j]-arr[i];//需要找的值//找到这个数并且其位置是在i下标之前if(xarr[i]hash.containsKey(x)){dp[i][j]dp[hash.get(x)][i]1;retMath.max(ret,dp[i][j]);}}}//可能构不成斐波那契子序列returnret3?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){intnnums.length;int[][]dpnewint[n][n];MapInteger,IntegerhashnewHashMap();//初始化for(inti0;in;i){for(intj0;jn;j){dp[i][j]2;}}hash.put(nums[0],0);intret2;for(inti1;in;i){//先确定倒数第二个数for(intji1;jn;j){//枚举最后一个数intx2*nums[i]-nums[j];//哈希表中找出一个满足等差的数if(hash.containsKey(x)){dp[i][j]dp[hash.get(x)][i]1;retMath.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){intnnums.length;int[][]dpnewint[n][n];int[]pairsnewint[n];//使用long类型计算过程中可能会溢出MapLong,ListIntegerhashnewHashMap();//将值和下标数组对应for(inti0;in;i){longtem(long)nums[i];if(!hash.containsKey(tem)){hash.put(tem,newArrayList());}hash.get(tem).add(i);}intsum0;for(intj2;jn;j){//倒数第一个数for(inti1;ij;i){//倒数第二个数longx2L*nums[i]-nums[j];if(hash.containsKey(x)){//所有符合要求的下标for(intk:hash.get(x)){if(ki){dp[i][j]dp[k][i]1;}else{//下标是递增存储不符合要求后面也都不符合break;}}sumdp[i][j];}}}returnsum;}}