首页 > 其他分享 >第九章 动态规划Part10

第九章 动态规划Part10

时间:2024-08-29 13:25:48浏览次数:11  
标签:nums 第九章 Part10 len result 序列 动态 nums1 dp

目录

任务

300. 最长递增子序列

子序列 是由数组派生而来的序列,删除(或不删除)数组中的元素而不改变其余元素的顺序。例如,[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列

思路

dp[i] 表示以索引i结尾的最长严格递增子序列长度,当符合条件时(比之前某个值大),它等于之前某个索引(以j结尾的)达到最长长度加1,不符合条件时(比之前所有值都小),最大长度为1。

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        dp = [1] * len(nums)
        result = 1
        for i in range(1,len(nums)):
            for j in range(i):
                if nums[i] > nums[j]:
                    dp[i] = max(dp[i],dp[j] + 1)
                result = dp[i] if result < dp[i] else result
        
        return result

674. 最长连续递增序列

给定一个未经排序的整数数组,找到最长且 连续递增的子序列,并返回该序列的长度。
连续递增的子序列 可以由两个下标 l 和 r(l < r)确定,如果对于每个 l <= i < r,都有 nums[i] < nums[i + 1] ,那么子序列 [nums[l], nums[l + 1], ..., nums[r - 1], nums[r]] 就是连续递增子序列。

思路

dp[i] 表示以i索引结尾的最长连续递增序列长度,与上题的区别是需要连续,更简单了,只需要与dp[i-1]比较即可

class Solution:
    def findLengthOfLCIS(self, nums: List[int]) -> int:
        dp = [1] * len(nums)
        result = 1
        for i in range(1,len(nums)):
                if nums[i] > nums[i-1]:
                    dp[i] = dp[i-1] + 1
                result = dp[i] if result < dp[i] else result
        
        return result

718. 最长重复子数组

给两个整数数组 nums1 和 nums2 ,返回 两个数组中 公共的 、长度最长的子数组的长度 。

思路

dp[i][j]表示 nums1 以i-1结尾,num2 以j-1结尾的最长重复子数组.这里的技巧是 表示i-1,j-1结尾,目的是可以避免首行首列的初始化时的麻烦。(如果表示i,j,则首行表示nums1以第一个数结尾的所有重复数字,同理,首列表示num2以第一个数结尾的所有重复数字,如果有则赋1,没有赋0,遍历赋值很麻烦) 而i-1,j-1 这样处理就可以直接全部赋0,不需要考虑上述问题。
当nums1[i-1] == nums2[j-1]时,dp[i][j] = dp[i-1][j-1] + 1,否则,dp[i][j] = 0

class Solution:
    def findLength(self, nums1: List[int], nums2: List[int]) -> int:
        dp = [[0] * (len(nums2)+1) for _ in range(len(nums1)+1)]
        result = 0
        for i in range(1,len(nums1) + 1):
            for j in range(1,len(nums2) + 1):
                if nums1[i-1] == nums2[j-1]:
                    dp[i][j] = dp[i-1][j-1] + 1
                    result = dp[i][j] if result < dp[i][j] else result
        return result

标签:nums,第九章,Part10,len,result,序列,动态,nums1,dp
From: https://www.cnblogs.com/haohaoscnblogs/p/18386472

相关文章

  • 【零信任方案】持续安全风险评估与动态访问控制实现方案
    一、为什么做持续安全风险评估与动态访问控制二、实现方案思路三、详细实现方案原创网络个人修炼一、为什么要持续进行安全风险评估和动态的访问控制访问控制是比较常见的安全隔离技术,我们这里主要讲网络访问的访问控制,其他文件存储读取访问等其他访问也是类似。传统......
  • 算法-动态规划-完全背包
    0.动态规划五部曲:确定dp数组(dptable)以及下标的含义确定递推公式dp数组如何初始化确定遍历顺序举例推导dp数组1.完全背包问题完全背包问题中,每个物品都有无数个,可以重复选择。二维dp数组int[][]dp=newint[n][totalWeight+1];for(inti=0;i<n;++i){fo......
  • Cesium展示——图标 billboard 动态变化
    文章目录需求分析1.导入2.加载billboard3.点击图标展示对应name属性4.实现动态变化4.上代码需求Cesium展示——图标动态变化分析1.导入importspjkfrom'./assets/spjk.png';2.加载billboardfunctionaddBillboard(lon......
  • Cesium 展示——动态洪水淹没效果
    文章目录需求分析1.引入插件2.定义变量3.开始绘制3.1绘制点3.2绘制线3.3绘制面3.4开始分析(第一种)3.5开始分析(第二种)3.6方法调用4.整体代码其他需求从低处到高处实现洪水淹没效果分析本篇文章对方法进行单独抽离,因此支持......
  • DLL动态库动态加载
    库的调用方式在VS下调用库有两种形式:- 静态加载 - 动态加载 静态加载下,对应的头文件、DLL和LIB缺一不可,并且产生的EXE没有找到DLL文件的话就会导致“应用程序初始化失败”。 动态加载下,只需要DLL,通过LoadLibrary()函数进行加载,但该方式对生成的dll的规范有一定的要求否......
  • 学习爬虫day29-瑞数动态安全
    过瑞数的基本方法:自动化工具(非常NB,如:selenuim,playwrite),补环境,纯算;浏览器开无痕模式今天学习深圳大学的案例。1、解决无限dubugger:断点设置:一律不在此处暂定(debugger),注入js,重写debugger;方法一:控制台输入以下代码并执行let_Function=function;Function=function(s){if......
  • 静态代理ip与动态代理ip的区别与选择
    在当今软件开发领域,代理模式作为一种重要的设计模式,广泛应用于增强现有对象功能、控制访问权限以及实现远程调用等场景。本文旨在深入探讨静态代理与动态代理之间的核心区别,帮助开发者理解两者在实现机制、灵活性、性能表现及适用场景上的异同,进而指导在实际项目中如何根据具体......
  • 动态调用vi和静态调用vi
    记一次被静态调用的vi打开运行卡死的问题:在一次上位机的调试中,主程序静态调用了子VI,提前打开子VI的情况下,运行主程序,使用相应功能时,子VI卡死无法操作。到网上查找相关问题后了解到这是labview中静态调用的一个弊端。同时,被静态调用的vi会随主程序启动而装载,从而增加资源消耗,影......
  • SpringBoot配置动态数据源 原理+实战
    若没空探究原理可直接跳转到“实现方式:注解+切面”目录数据源切换方法Spring对数据源的管理类似于策略模式,不懂策略模式也没关系,其实就是有一个全局的键值对,类型是Map<String,DataSource>。当JDBC操作数据库之时,会根据不同的key值选择不同的数据源。而这个key值可以放到方法的......
  • Java后端微服务架构下的配置动态刷新:Spring Cloud Bus
    Java后端微服务架构下的配置动态刷新:SpringCloudBus大家好,我是微赚淘客返利系统3.0的小编,是个冬天不穿秋裤,天冷也要风度的程序猿!在微服务架构中,服务的配置管理是一个挑战,尤其是当配置需要动态更新时。SpringCloudBus提供了一种基于消息总线的配置刷新机制,允许配置更改在服务......