首页 > 其他分享 >动态规划之——最长递增子序列

动态规划之——最长递增子序列

时间:2022-08-31 14:37:55浏览次数:83  
标签:index 数字 递增 numbers 序列 最长 dp

最长递增子序列(Longest Increasing Subsequence)是指在给定的一组数字中,按照从左向右顺序,由递增的数字组成的子序列(中间可以有间隔)中,取长度最大的子序列即为最长递增子序列。

如给定“1 2 4 3”,则递增的子序列有“1 2”、“1 4”、“1 3”、“2 4”、“2 3”、“1 2 4”、“1 2 3”,则最长的为“1 2 4”和“1 2 3”,长度为3。

 

如何求这个最长递增子序列呢?

由于是递增序列,数字往右是不断变大的,左侧的数必然小于右侧数,即最右侧的数字是最大的。

我们先分析个简单的例子“1 2 4”:

4左侧为“1 2”,都小于4,如果不考虑1 2之间的大小关系(即无论组合是1 4、2 4还是1 2 4),则4左侧至少有一个数字可以组成递增子序列,最长递增子序列至少为2(加上4自身长度1)。即只要左侧存在小于4的数字,就会导致递增子序列的长度增加。

我们再往回看数字2,位于整个序列的第二位,因此它只需要对比一次,2大于1,所以截止到“2”这个数字,最长递增子序列长度为2,且这个长度是固定的,即后续数字无论如何组合,也不会影响2和之前数字1构成的最长递增子序列(子问题的最优解)。

也就说明后续如果有数字大于2,可以参考这个最长递增子序列。

这时我们再返回到4,4大于2,因此可以直接取左侧小于4的数字对应的最长递增子序列,再加1后就是当前的最长递增子序列,如图-1,顶部的红色数字表示对应序列中数字的最长递增子序列的长度。

                                            图-1

但还有可能是,左侧数字小于4的可能有多个,距离4最近的不一定就是最长的,因此需要挨个对比这些数字的最大递增子序列,取一个最大值。如图-2中的演示数据,这里显然要取4左侧的“3”对应的最长子序列长度,而不是“1”的对应值。

                                                         图-2

因此我们总结出如下步骤:

1 从左侧开始处理数字,且每个数字对应的默认最长子序列都是1。

2 从第二个数字a开始,在左侧所有小于a的数字的最长子序列长度中,取最大的长度+1,即为当前最长递增子序列的长度。

3 后续数字参考步骤2依次处理。

我们先用递归的方式来实现,代码如下。对应演示数据为“5, 2, 8, 6, 3, 6, 9, 5”

 1 import java.util.Arrays;
 2 
 3 public class LongestIncreasingSubsequence {
 4     public static void main(String[] args) {
 5         int[] numbers = {5, 2, 8, 6, 3, 6, 9, 5};
 6         System.out.println(Arrays.toString(numbers));
 7         recursive(numbers);
 8     }
 9 
10     public static void recursive(int[] numbers) {
11         //从左到右依次计算截止到每个数字的最长递增子序列的长度
12         for (int i = 0; i < numbers.length; i++) {
13             System.out.printf("index=%d num=%d max=%d\n", i, numbers[i], cmp(numbers, i));
14         }
15     }
16 
17     private static int cmp(int[] numbers, int k) {
18         //数据中第一个位置的最长子序列是1
19         if (k == 0) {
20             return 1;
21         }
22         //小于当前数字(基准数字)的列表中最大的子序列长度,默认长度为1
23         int max = 1;
24         //从左侧第一个位置开始依次和基准数字对比
25         for (int i = 0; i < k; i++) {
26             //小于基准数字,说明可以组成递增子序列
27             if (numbers[i] < numbers[k]) {
28                 //取截至到k对应数字的最大子序列长度。反应到当前基准数字的列长度需要返回结果+1
29                 int length = cmp(numbers, i) + 1;
30                 //取所有小于基准数字中最大的那一个数
31                 if (length > max) {
32                     max = length;
33                 }
34             }
35         }
36         return max;
37     }
38 }

 输出

[5, 2, 8, 6, 3, 6, 9, 5]
index=0 num=5 max=1
index=1 num=2 max=1
index=2 num=8 max=2
index=3 num=6 max=2
index=4 num=3 max=2
index=5 num=6 max=3
index=6 num=9 max=4
index=7 num=5 max=3

可以看到第29行的 cmp(numbers, i) + 1,是通过递归获取依赖的最长递增子序列。而由于外层循环变量 i 每次都从0开始,就可能存在重复调用。因此我们可以参考动态规划方法做一些优化,代码如下。

 1     public static void dp(int[] numbers) {
 2         //保存每个数字的下标对应的最长递增子序列长度值
 3         int[] dp = new int[numbers.length];
 4         //数据初始化:每个数字对应的默认序列长度都是1
 5         for (int i = 0; i < dp.length; i++) {
 6             dp[i] = 1;
 7         }
 8         System.out.println(Arrays.toString(dp));
 9 
10         //由于第一个位置(index=0)不存在前驱数字,也就无需比较,直接从index=1开始即可。
11         for (int i = 1; i < numbers.length; i++) {
12             System.out.printf("index=%d num=%d\n", i, numbers[i]);
13             //当前数字和之前的依次比较
14             for (int j = 0; j < i; j++) {
15                 //小于当前数字说明是一个递增序列,序列长度可以加1
16                 if (numbers[i] > numbers[j]) {
17                     System.out.printf("\t%d>%d dp[%d]=%d dp[%d]=%d\n", numbers[i], numbers[j], i, dp[i], j, dp[j]);
18                     //但需要取最大的
19                     if (dp[j] + 1 > dp[i]) {
20                         dp[i] = dp[j] + 1;
21                     }
22                 } else {
23                     System.out.printf("\t%d<=%d skip\n", numbers[i], numbers[j]);
24                 }
25             }
26             System.out.printf("\tdp[%d]=%d %s\n", i, dp[i], Arrays.toString(dp));
27         }
28     }

增加对应调用dp(numbers),输出如下

[dp]
[1, 1, 1, 1, 1, 1, 1, 1]
index=1 num=2
	2<=5 skip
	dp[1]=1 [1, 1, 1, 1, 1, 1, 1, 1]
index=2 num=8
	8>5 dp[2]=1 dp[0]=1
	8>2 dp[2]=2 dp[1]=1
	dp[2]=2 [1, 1, 2, 1, 1, 1, 1, 1]
index=3 num=6
	6>5 dp[3]=1 dp[0]=1
	6>2 dp[3]=2 dp[1]=1
	6<=8 skip
	dp[3]=2 [1, 1, 2, 2, 1, 1, 1, 1]
index=4 num=3
	3<=5 skip
	3>2 dp[4]=1 dp[1]=1
	3<=8 skip
	3<=6 skip
	dp[4]=2 [1, 1, 2, 2, 2, 1, 1, 1]
index=5 num=6
	6>5 dp[5]=1 dp[0]=1
	6>2 dp[5]=2 dp[1]=1
	6<=8 skip
	6<=6 skip
	6>3 dp[5]=2 dp[4]=2
	dp[5]=3 [1, 1, 2, 2, 2, 3, 1, 1]
index=6 num=9
	9>5 dp[6]=1 dp[0]=1
	9>2 dp[6]=2 dp[1]=1
	9>8 dp[6]=2 dp[2]=2
	9>6 dp[6]=3 dp[3]=2
	9>3 dp[6]=3 dp[4]=2
	9>6 dp[6]=3 dp[5]=3
	dp[6]=4 [1, 1, 2, 2, 2, 3, 4, 1]
index=7 num=5
	5<=5 skip
	5>2 dp[7]=1 dp[1]=1
	5<=8 skip
	5<=6 skip
	5>3 dp[7]=2 dp[4]=2
	5<=6 skip
	5<=9 skip
	dp[7]=3 [1, 1, 2, 2, 2, 3, 4, 3]

最终各数字的依赖关系如图-3:

                                                                                                              图-3

从图-3中可以看到,这些数字可以理解为数据结构“图”中的“顶点”,对应为一张有向无环图,每个顶点的前驱顶点都是固定的(由序列本身的顺序来决定),依赖关系由它前驱顶点(小于顶点值的数)决定。

 

参考资料

最长递增子序列

Longest increasing subsequence

动态规划解决问题的5个简单步骤

标签:index,数字,递增,numbers,序列,最长,dp
From: https://www.cnblogs.com/binary220615/p/16642165.html

相关文章

  • leetcode 409 Longest Palindrome 最长回文串(简单)
    一、题目大意给定一个包含大写字母和小写字母的字符串s,返回通过这些字母构造成的最长的回文串。在构造过程中,请注意区分大小写。比如"Aa"不能当做一个回文字符......
  • 序列化器:反序列换-添加和更新数据操作
    前端传到后端需要反序列化,后端传到前端需要序列化正常需要serializer两次:fromdjango.viewsimportViewfrom.modelsimportStudentfrom.serializersimportStude......
  • TimescaleDB时间序列数据库
    TimescaleDB:这是一款支持完整sql开源的时间序列数据库。用处1、数据量庞大2、只做时间索引类的插入3、很少更新数据TimescaleDB的好处:基于时序优化自动分片(自动......
  • [网鼎杯 2020 朱雀组]phpweb-1|反序列化
    1、打开界面之后界面一直在刷新,检查源代码也未发现提示信息,但是在检查中发现了两个隐藏的属性:func和p,抓包进行查看一下,结果如下:2、对两个参数与返回值进行分析,我们使用d......
  • 序列与反序列
    特殊的对象想要存储时,就需要使用序列1importpickle23info={4'':'',5'age':32,6'func':'xxx'7}89m=1001011print(pickle.d......
  • 求一个图的最打的半联通子集=求一个图的最长链方案和个数
    拓扑图最长路等于背包问题求方案数因为要求点不同存在多条边同一情况需要边判重(set)拓扑求方案数#include<iostream>#include<cstring>#include<algorithm>......
  • civil3d安装教程2022序列号和密钥
     Civil3D2021WIN1064位安装步骤:1.先使用“百度网盘客户端”下载C3D21_CN_x64软件安装包到电脑磁盘里,并右击进行解压,安装前先断网,然后找到Autodesk_Civil_3D_2021_Chin......
  • ARIMA时间序列模型,确定合适的 p 和 q 值
    图3自相关图、偏相关图通过观察图3中的acf图和pacf图,可以得到:自相关图显示滞后有三个阶超出了置信边界(第一条线代表起始点,不在滞后范围内);偏相关图显示在滞后1......
  • 序列化器:反序列换-字段选项 validate validate_<字段> validator
    1.使用序列化器进行反序列化时,需要对数据进行验证后,才能获取验证成功的数据或保存成模型类对象。2.在获取反序列化的数据前,必须调用is_valid()方法进行验证,验证成功返回Tr......
  • P4551 最长异或路径
    给定树上\(n\)个点和边权,求两点间所有边权的异或和最大。\(n\leq10^5\)。首先如果假定一个根,那么所有点到根的距离\(dis[i]\)中两两异或得到的就是答案。(\(x,y\)......