动态规划 之 子序列系列 算法专题

news/2024/11/17 10:45:18/

一. 最长递增子序列

最长递增子序列

  1. 状态表示
    dp[i] 表示以i位置为结尾, 最长的递增子序列
  2. 状态转移方程
    1.如果以i位置为开头 那么长度为1
    2.如果以i位置结尾, 由于不知道从前面哪一个位置取子序列, 所以要定义一个j(0 <= j <= i - 1), 找到以j位置结尾的所有子序列中, 最长的, 即dp[j]
  • dp[i] = dp[j] + 1
  1. 初始化
    可以先全部初始化为1
  2. 填表顺序
    从左往右
  3. 返回值
    返回dp表中的最大值
class Solution {public int lengthOfLIS(int[] nums) {int n = nums.length;int[] dp = new int[n];Arrays.fill(dp, 1);int ret = 1;for(int i = 1; i < n; i++){int max = 1;for(int j = 0; j < i; j++){if(nums[j] < nums[i]){dp[i] = Math.max(dp[j] + 1, dp[i]);}} ret = Math.max(dp[i], ret);}return ret;}
}

二. 摆动序列

摆动序列

  1. 状态表示
    f[i] 表示以i位置为结尾, 最后呈"上升"趋势最长的摆动序列
    g[i] 表示以i位置为结尾, 最后呈"下降"趋势最长的摆动序列
  2. 状态转移方程
    1.如果以i位置为开头 那么长度为1
    2.如果以i位置结尾, 由于不知道从前面哪一个位置取子序列, 所以要定义一个j(0 <= j <= i - 1), 找到以j位置结尾的所有子序列中, 最长的, 即dp[j]
    if(nums[j] < nums[i]){
    f[i] = Math.max(g[j] + 1, f[i]);
    }else if(nums[j] > nums[i]){
    g[i] = Math.max(f[j] + 1, g[i]);
    }
  3. 初始化
    可以先全部初始化为1
  4. 填表顺序
    从左往右
  5. 返回值
    返回dp表中的最大值
class Solution {public int wiggleMaxLength(int[] nums) {int n = nums.length;int[] f = new int[n];int[] g = new int[n];Arrays.fill(f, 1);Arrays.fill(g, 1);int ret = 1;for(int i = 1; i < n; i++){for(int j = 0; j < i; j++){if(nums[j] < nums[i]){f[i] = Math.max(g[j] + 1, f[i]);}else if(nums[j] > nums[i]){g[i] = Math.max(f[j] + 1, g[i]);}ret = Math.max(ret, Math.max(f[i], g[i]));}}return ret;}
}

三. 最长数对链

最长数对链
前置处理: 为了保证使用动态规划, 填表顺序是从左往右, 所以要先对数组进行排序, 只需要根据第一个数进行排序即可, 保证选择i位置时, 不会选到i后面的位置

  1. 状态表示
    dp[i] 表示以i位置为结尾, 最长数对链
  2. 状态转移方程
    1.如果以i位置为开头 那么长度为1
    2.如果以i位置结尾, 由于不知道从前面哪一个位置取子序列, 所以要定义一个j(0 <= j <= i - 1), 找到以j位置结尾的所有子序列中, 最长的, 即dp[j]
  • dp[i] = dp[j] + 1
  1. 初始化
    可以先全部初始化为1
  2. 填表顺序
    从左往右
  3. 返回值
    返回dp表中的最大值
class Solution {public int findLongestChain(int[][] pairs) {Arrays.sort(pairs, (a, b) -> a[0] - b[0]);int n = pairs.length;int[] dp = new int[n];Arrays.fill(dp, 1);int ret = 1;for(int i = 1; i < n; i++){for(int j = 0; j < i; j++){if(pairs[j][1] < pairs[i][0]){dp[i] = Math.max(dp[i], dp[j] + 1);}ret = Math.max(dp[i], ret);}}return ret;}
}

四. 最长定差子序列

最长定差子序列

  1. 状态表示
    dp[i] 表示以i位置为结尾, 最长定差子序列
  2. 状态转移方程
    1.如果以i位置为开头 那么长度为1
    2.如果以i位置结尾, 由于不知道从前面哪一个位置取子序列, 所以要定义一个j(0 <= j <= i - 1), 找到以j位置结尾的所有子序列中, 最长的, 即dp[j]
    只需要找到在前面中, 大小为arr[i] - difference 即可, 并且由于找的值是固定的, 那么我们只需要找到前面的其中一个即可

所以我们可以将dp表放在hash表中

  1. 初始化
    可以先全部初始化为1(在写代码时有技巧)
  2. 填表顺序
    从左往右
  3. 返回值
    返回dp表中的最大值
class Solution {public int longestSubsequence(int[] arr, int difference) {//创建一个hash表, 在hash表中做dpMap<Integer, Integer> hash = new HashMap<>();//arr[i], dp[i]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;//下面的方法超时// int n = arr.length;// int[] dp = new int[n];// Arrays.fill(dp, 1);// int ret = 1;// for(int i = 1; i < n; i++){//     for(int j = 0; j < i; j++){//         if(arr[i] - arr[j] == difference){//             dp[i] = Math.max(dp[i], dp[j] + 1);//         }//         ret = Math.max(ret, dp[i]);//     }// }// return ret;}
}

五. 最长的斐波那契子序列的长度

最长的斐波那契子序列的长度

  1. 状态表示
    dp[i] 表示以i位置为结尾, 最长斐波那契子序列的长度, 这样我们并不知道前面两个数是谁, 所以我们可以固定两个位置, 以i和j位置为结尾, 这样就可以找到k位置

  2. 状态转移方程
    如果找到k位置, 并且这个位置在i, j的前面, 那么dp[i][j] = dp[k][i] + 1

因为要频繁查找k的位置, 可以将arr中下标和值的映射关系放在hash表中

  1. 初始化
    可以先全部初始化为2
  2. 填表顺序
    从上往下
  3. 返回值
    返回dp表中的最大值, 但是如果找不到斐波那契序列, 那么应该返回0
class Solution {public int lenLongestFibSubseq(int[] arr) {int n = arr.length;Map<Integer, Integer> hash = new HashMap<>();for(int i = 0; i < n; i++){hash.put(arr[i], i);} int ret = 2;int[][] dp = new int[n][n];for(int i = 0; i < n; i++){for(int j = 0; j < n; j++){dp[i][j] = 2;}}for(int i = 2; i < n; i++){for(int j = 1; j < i; j++){int a = arr[i] - arr[j];if(a < arr[j] && hash.containsKey(a))dp[j][i] = dp[hash.get(a)][j] + 1;ret = Math.max(dp[j][i], ret);}}return ret == 2 ? 0 : ret;}
}

http://www.ppmy.cn/news/1547704.html

相关文章

AndroidStudio-Activity的生命周期

一、Avtivity的启动和结束 从当前页面跳到新页面&#xff0c;跳转代码如下&#xff1a; startActivity(new Intent(源页面.this&#xff0c;目标页面.class))&#xff1b; 从当前页面回到上一个页面&#xff0c;相当于关闭当前页面&#xff0c;返回代码如下&#xff1a; finis…

【视频讲解】Python深度神经网络DNNs-K-Means(K-均值)聚类方法在MNIST等数据可视化对比分析...

全文链接&#xff1a;https://tecdat.cn/?p38289 分析师&#xff1a;Cucu Sun 近年来&#xff0c;由于诸如自动编码器等深度神经网络&#xff08;DNN&#xff09;的高表示能力&#xff0c;深度聚类方法发展迅速。其核心思想是表示学习和聚类可以相互促进&#xff1a;好的表示会…

thinkphp 连表查询

在ThinkPHP中&#xff0c;可以使用Query类的join方法来进行连表查询。连表查询可以用于在查询结果中包含多个表的数据&#xff0c;以便获取更丰富的信息。 以下是一个简单的例子&#xff0c;假设有两个表user和order&#xff0c;我们想要查询用户的订单信息&#xff1a; $use…

sqlsever 分布式存储查询

当数据存储在不同的服务器上的时候怎么取出来进行正常管连呢?比如你有 A 和B 两个服务器 里面存有两个表 分别是 A_TABLE、B_TABLE 其中 他们的关联关系是 ID 互相关联 1.创建链接服务器如果在B数据库要访问A数据库 那么 就在B数据库创建 -- 创建链接服务器 EXEC sp_addlink…

Vue 组件通信及进阶语法

文章目录 一、scoped 样式冲突二、data 是一个函数三、组件通信1. 父子通信1.1 props 校验1.2 props 比较 data 2. 非父子通信2.1 event bus2.2 provide-inject 四、进阶语法1. v-model 详解2. sync 修饰符3. ref 和 $refs4. $nextTick 一、scoped 样式冲突 注意点&#xff1a;…

LeetCode --- 143周赛

题目列表 3345. 最小可整除数位乘积 I 3346. 执行操作后元素的最高频率 I 3347. 执行操作后元素的最高频率 II 3348. 最小可整除数位乘积 II 一、最小可整除数位成绩I 由于本题的数据范围比较小&#xff0c;我们直接暴力枚举即可&#xff0c;代码如下 class Solution { p…

Pytest从入门到精通

一、pytest单元测试框架 (1)什么是单元测试框架 单元测试是指在软件开发当中,针对软件的最小单位(函数,方法)进行正确性的检查测试。 (2)单元测试框架 java : junit和testng python : unittest和pytest (3)单元测试框架主要做什么? 1.测试发现:从多个文件里面去找到我们测试…

python 同时控制多部手机

在这个智能时代,我们的手机早已成为生活和工作中不可或缺的工具。无论是管理多个社交媒体账号,还是处理多台设备上的事务,如何更高效地控制多个手机成为了每个人的痛点。 今天带来的这个的软件为你提供了一键控制多部手机的强大功能。无论是办公、娱乐,还是社交,你都能通过…