💕"你可以说我贱，但你不能说我的爱贱。"💕
作者：Mylvzi
文章主要内容：算法系列–动态规划–子序列(2)
今天带来的是
算法系列--动态规划--子序列(2),包含了关于子序列问题中较难的几道题目(尤其是通过二维状态表示来推导状态转移方程)
1.最⻓定差⼦序列
链接:
https://leetcode.cn/problems/longest-arithmetic-subsequence-of-given-difference/description/
分析:
- 状态表示:dp[i]:
以i为结尾的,最长的定差子序列的长度 - 状态转移方程:
if(hash.contains(a - difference)) dp[i] = dp[k] + 1 - 优化:由于要寻找
a-difference与其对应的下标k,所以我们可以利用一个哈希表来建立数值与下标之间的映射关系
代码:
class Solution { public int longestSubsequence(int[] arr, int difference) { Map<Integer,Integer> hash = new HashMap<>(); int ret = 1;// 记录最值 for(int a : arr) { hash.put(a,hash.getOrDefault(a-difference, 0 ) + 1);// 将当前位置插入到哈希表中 ret = Math.max(ret,hash.get(a));// 更新最值 } return ret; } }
2.最⻓的斐波那契⼦序列的⻓度
链接:
https://leetcode.cn/problems/length-of-longest-fibonacci-subsequence/
分析:
代码:
class Solution { public int lenLongestFibSubseq(int[] nums) { int n = nums.length; int[][] dp = new int[n][n]; // 初始化为2 for(int i = 0; i < n; i++) { for(int j = 0; j < n; j++) dp[i][j] = 2; } Map<Integer,Integer> hash = new HashMap<>(); for(int i = 0; i < n; i++) hash.put(nums[i], i);// 将数组中的值和下标存入到哈希表之中 hash.put(nums[0],0); int ret = 2; // 填表 for(int j = 1; j < n; j++) { for(int i = 0; i < j; i++) { int a = nums[j] - nums[i];// 得到前一个位置的数 if(a < nums[i] && hash.containsKey(a)) {//必须包含 且下标在i之前 dp[i][j] = dp[hash.get(a)][i] + 1;// 更新 } ret = Math.max(ret,dp[i][j]);// 更新最值 } } return ret < 3 ? 0 : ret;// 处理极端情况(无fib数列) } }
算法系列--动态规划--子序列(2)（下）https://developer.aliyun.com/article/1480801?spm=a2c6h.13148508.setting.28.361f4f0eyTL4lb
