动态规划算法学习四:最大上升子序列问题(LIS:Longest Increasing Subsequence)

简介: 这篇文章介绍了动态规划算法中解决最大上升子序列问题(LIS)的方法,包括问题的描述、动态规划的步骤、状态表示、递推方程、计算最优值以及优化方法,如非动态规划的二分法。

前言

一、问题描述

在这里插入图片描述
在这里插入图片描述

二、DP步骤

1、最优子结构

  • 给定序列𝑆=[𝑠1,𝑠2,,𝑠𝑛],如果子序列[𝑆(𝑖1 ),𝑆(𝑖2 ), ⋯,𝑆(𝑖𝑘)]是其最大上升子序列,则[𝑆(𝑖1 ),𝑆(𝑖2 ), ⋯,𝑆(𝑖(𝑘−1) )]是子问题𝑆=[𝑠1,𝑠2,⋯,𝑆(𝑖(𝑘−1) )]的最大上升子序列吗?
  • 例:给定 S = [1, 3, 4, 2, 7, 9, 6, 8],最大上升子序列可为 [1, 3, 4, 6, 8],最大长度为5。
  • [1, 3, 4, 6]显然不是[1, 3, 4, 2, 7, 9, 6]的最大上升子序列,因为[1, 3, 4, 7, 9]是其最大上升子序列。
    注意:可以同时有多个最大上升子序列!每个的最大值都不相同
  • 如果直接把最大上升子序列的长度作为规划目标,那么该问题不具备最优子结构性质(因为可能同时有多个最大上升子序列,使得最优子结构不成立)。只能采用间接的办法,引入一些中间目标作为动态规划的对象。

a、限界上升子序列

在这里插入图片描述
在这里插入图片描述

b、最优子结构性质

在这里插入图片描述
在这里插入图片描述

2、状态表示和递推方程

在这里插入图片描述
在这里插入图片描述
公式讲解:只求长度,不求具体的子序列

  • 逐一找出1—(m-1)个元素中所有小于Sm的元素Si及其对应的Len(Si)值,然后从中取最大的一个Len(.)值,然后加1。【 1–i个元素中所有大于Sm的元素的Len(.)值全都不予考虑】

  • 如果精简为max{Len(i)+1 | 1≤i<m, Sm<Si},可以吗?
    sure

3、计算最优值

  • 𝐿𝑒𝑛(𝑚)的计算同样按照自底向上的顺序进行:所有子问题的总数为n个(即,分别以每个元素为限界);m越小,其子问题𝐿𝑒𝑛(𝑚)求解的复杂度就越低
  • 当所有的𝐿𝑒𝑛(𝑚)(1≤𝑚≤𝑛)都计算完毕后,统计其中最大值,即可得到输入序列 S 的最大上升子序列
  • 注意:最大上升子序列的长度不一定等于𝑳𝒆𝒏(𝒏)
    在这里插入图片描述
    答案详解:
  1. Len(1) = 1
  2. Len(3) = 2:找到3之前小于3的数字中,最大的Len(.)值加1,即:len(1)+1=1。
  3. Len(4)=3:找到4之前小于4的数字:1和3,最大Len(.)值加1,即:len(3)+1=3。
  4. Len(2)=2:找到2之前小于2的数字:1,最大Len(.)值加1,即:Len(1)+1=2。
  5. Len(7)=4:找到7之前小于7的数字:1,3,4,2,最大Len(.)值加1,即:Len(4)+1=4。
  6. Len(6)=4:找到6之前小于6的数字:1,3,4,2,最大Len(.)值加1,即:Len(4)+1=4。
  7. Len(8)=5:找到8之前小于8的数字:1,2,3,2,7,6,最大Len(.)值加1,即:Len(7)+1=5 或者 Len(6)+1=5

4、算法实现

时间复杂度:n2

/**
 * DP算法之最大上升子序列问题
 */
public class Main4 {
    public static int MAXN = 100;
    public static void main(String[] args) {
        int[] seqSrc = {1, 3, 4, 2, 7, 6, 8};
        int i = LISLength(7, seqSrc);
        System.out.println(i);
    }

    public static int LISLength(int num, int[] seqSrc) {
        int[] Len = new int[MAXN];
        int res = 1;
        //设第m个数的值为上界
        for (int m = 0; m < num; m++) {  
            //每个新m为上界时,Len[m]总是从1开始
            Len[m] = 1;     
            for (int i = 0; i < m; i++)
                //遍历所有以第i个数为上界的长度,从中选出符合max公式条件的最大值加1,就是Len[m]。
                if (seqSrc[i] < seqSrc[m] && Len[i] + 1 > Len[m])   
                    Len[m] = Len[i] + 1;
            //记录从len[1]到len[m]中的最大值,res为最大公共子序列长度,最后的解
            res = (res > Len[m] ? res : Len[m]);  
        }
        return res;
    }
}
AI 代码解读

在这里插入图片描述
代码解说:

  1. 第一个for遍历:有几个元素就遍历几个,计算每个的Len(.)值。
  2. 第二个for遍历:遍历当前元素的最大Len(.)值。
    • seqSrc[i] < seqSrc[m] :过滤小于当前元素的值,
    • Len[i] + 1 > Len[m]:找到最大值

三、优化:非DP /二分法

时间复杂度 nlog2n。

1、新问题

在这里插入图片描述
上图中的公式中的 i ,为数组的下标
例:

  1. k = 4 的值有两个,Len(5) = 4,Len(6) = 4
  2. S[5] = 7, S[6] = 6
  3. 所以 T[k=4] = 6。
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

2、算法实现

/**
 * DP之最大上升子序列:时间复杂度  nlog2n
 */
public class Main5 {

    public static void main(String[] args) {
        int[] seqSrc = {1, 3, 4, 2, 7, 6, 8};
        int i = lengthOfLIS(seqSrc);
        System.out.println(i);
    }

    public static int lengthOfLIS(int[] arr) {
        if (arr == null || arr.length == 0) {
            return 0;
        }
        int[] ends = new int[arr.length];
        ends[0] = arr[0];
        int right = 0;
        int l = 0;
        int r = 0;
        int m = 0;
        int max = 1;
        for (int i = 1; i < arr.length; i++) {
            l = 0;
            r = right;
            while (l <= r) {
                m = (l + r) / 2;
                if (arr[i] > ends[m]) {
                    l = m + 1;
                } else {
                    r = m - 1;
                }
            }
            right = Math.max(right, l);
            ends[l] = arr[i];
            max = Math.max(max, l + 1);
        }
        return max;
    }
}
AI 代码解读

在这里插入图片描述

目录
打赏
0
2
2
0
49
分享
相关文章
基于改进遗传优化的BP神经网络金融序列预测算法matlab仿真
本项目基于改进遗传优化的BP神经网络进行金融序列预测,使用MATLAB2022A实现。通过对比BP神经网络、遗传优化BP神经网络及改进遗传优化BP神经网络,展示了三者的误差和预测曲线差异。核心程序结合遗传算法(GA)与BP神经网络,利用GA优化BP网络的初始权重和阈值,提高预测精度。GA通过选择、交叉、变异操作迭代优化,防止局部收敛,增强模型对金融市场复杂性和不确定性的适应能力。
208 80
架构学习:7种负载均衡算法策略
四层负载均衡包括数据链路层、网络层和应用层负载均衡。数据链路层通过修改MAC地址转发帧;网络层通过改变IP地址实现数据包转发;应用层有多种策略,如轮循、权重轮循、随机、权重随机、一致性哈希、响应速度和最少连接数均衡,确保请求合理分配到服务器,提升性能与稳定性。
238 11
架构学习:7种负载均衡算法策略
|
29天前
|
【潜意识Java】蓝桥杯算法有关的动态规划求解背包问题
本文介绍了经典的0/1背包问题及其动态规划解法。
48 5
基于遗传优化的双BP神经网络金融序列预测算法matlab仿真
本项目基于遗传优化的双BP神经网络实现金融序列预测,使用MATLAB2022A进行仿真。算法通过两个初始学习率不同的BP神经网络(e1, e2)协同工作,结合遗传算法优化,提高预测精度。实验展示了三个算法的误差对比结果,验证了该方法的有效性。
2024重生之回溯数据结构与算法系列学习之串(12)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丟脸好嘛?】
数据结构与算法系列学习之串的定义和基本操作、串的储存结构、基本操作的实现、朴素模式匹配算法、KMP算法等代码举例及图解说明;【含常见的报错问题及其对应的解决方法】你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
2024重生之回溯数据结构与算法系列学习之串(12)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丟脸好嘛?】
【EMNLP2024】基于多轮课程学习的大语言模型蒸馏算法 TAPIR
阿里云人工智能平台 PAI 与复旦大学王鹏教授团队合作,在自然语言处理顶级会议 EMNLP 2024 上发表论文《Distilling Instruction-following Abilities of Large Language Models with Task-aware Curriculum Planning》。
|
3月前
|
在Python编程中,分治法、贪心算法和动态规划是三种重要的算法。分治法通过将大问题分解为小问题,递归解决后合并结果
在Python编程中,分治法、贪心算法和动态规划是三种重要的算法。分治法通过将大问题分解为小问题,递归解决后合并结果;贪心算法在每一步选择局部最优解,追求全局最优;动态规划通过保存子问题的解,避免重复计算,确保全局最优。这三种算法各具特色,适用于不同类型的问题,合理选择能显著提升编程效率。
81 2
2024重生之回溯数据结构与算法系列学习之栈和队列精题汇总(10)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第3章之IKUN和I原达人之数据结构与算法系列学习栈与队列精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
基于FPGA的图像双线性插值算法verilog实现,包括tb测试文件和MATLAB辅助验证
本项目展示了256×256图像通过双线性插值放大至512×512的效果,无水印展示。使用Matlab 2022a和Vivado 2019.2开发,提供完整代码及详细中文注释、操作视频。核心程序实现图像缩放,并在Matlab中验证效果。双线性插值算法通过FPGA高效实现图像缩放,确保质量。
基于Retinex算法的图像去雾matlab仿真
本项目展示了基于Retinex算法的图像去雾技术。完整程序运行效果无水印,使用Matlab2022a开发。核心代码包含详细中文注释和操作步骤视频。Retinex理论由Edwin Land提出,旨在分离图像的光照和反射分量,增强图像对比度、颜色和细节,尤其在雾天条件下表现优异,有效解决图像去雾问题。

热门文章

最新文章

AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等