算法系列--动态规划--子序列(2)(上)

简介: 算法系列--动态规划--子序列(2)

💕"你可以说我贱,但你不能说我的爱贱。"💕

作者: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


目录
相关文章
|
5天前
|
存储 算法
数据结构与算法之动态规划--旷工问题
数据结构与算法之动态规划--旷工问题
9 1
|
6天前
|
机器学习/深度学习 存储 算法
LeetCode题目 90:五种算法 回溯\迭代\位掩码\字典树\动态规划实现 子集ll
LeetCode题目 90:五种算法 回溯\迭代\位掩码\字典树\动态规划实现 子集ll
|
6天前
|
算法 数据挖掘 开发者
LeetCode题目55:跳跃游戏【python5种算法贪心/回溯/动态规划/优化贪心/索引哈希映射 详解】
LeetCode题目55:跳跃游戏【python5种算法贪心/回溯/动态规划/优化贪心/索引哈希映射 详解】
|
6天前
|
SQL 算法 数据可视化
python 贪心算法 动态规划实现 跳跃游戏ll【力扣题45】
python 贪心算法 动态规划实现 跳跃游戏ll【力扣题45】
|
6天前
|
存储 SQL 算法
解锁动态规划:从斐波那契到高效算法
解锁动态规划:从斐波那契到高效算法
|
9天前
|
存储 算法
动态规划与搜索算法
动态规划与搜索算法
11 0
|
10天前
|
算法 Java Go
【经典算法】LeetCode 392 判断子序列(Java/C/Python3/Go实现含注释说明,Easy)
【经典算法】LeetCode 392 判断子序列(Java/C/Python3/Go实现含注释说明,Easy)
14 0
|
12天前
|
算法
【算法优选】 动态规划之两个数组dp——壹
【算法优选】 动态规划之两个数组dp——壹
|
12天前
|
人工智能 算法
【算法优选】 动态规划之子数组、子串系列——贰
【算法优选】 动态规划之子数组、子串系列——贰
|
12天前
|
机器学习/深度学习 算法 测试技术
【算法优选】 动态规划之子数组、子串系列——壹
【算法优选】 动态规划之子数组、子串系列——壹