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

第九章 动态规划Part11

时间:2024-08-29 13:47:52浏览次数:12  
标签:第九章 Part11 len 字符串 range 序列 动态 nums1 dp

目录

任务

1143. 最长公共子序列

给定两个字符串 text1 和 text2,返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ,返回 0 。

一个字符串的 子序列 是指这样一个新的字符串:它是由原字符串在不改变字符的相对顺序的情况下删除某些字符(也可以不删除任何字符)后组成的新字符串。

例如,"ace" 是 "abcde" 的子序列,但 "aec" 不是 "abcde" 的子序列。
两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。

思路

同718. 最长重复子数组,只是这里将连续的数组换成了不连续的子序列,dp[i][j]表示 nums1 以i-1结尾,num2 以j-1结尾的最长公共子序列
相等时同样用dp[i-1][j-1]+1来拓展长度。
区别是在当前不相等时,用两数组前一个索引所表示dp的较大值来保持已有长度。

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        dp = [[0] * (len(text2)+1) for _ in range(len(text1)+1)]
        for i in range(1,len(text1) + 1):
            for j in range(1,len(text2) + 1):
                if text1[i-1] == text2[j-1]:
                    dp[i][j] = dp[i-1][j-1] + 1
                else:
                    dp[i][j] = max(dp[i][j-1],dp[i-1][j])
                
        return dp[len(text1)][len(text2)]

1035. 不相交的线

在两条独立的水平线上按给定的顺序写下 nums1 和 nums2 中的整数。
现在,可以绘制一些连接两个数字 nums1[i] 和 nums2[j] 的直线,这些直线需要同时满足:
nums1[i] == nums2[j]
且绘制的直线不与任何其他连线(非水平线)相交。
请注意,连线即使在端点也不能相交:每个数字只能属于一条连线。
以这种方法绘制线条,并返回可以绘制的最大连线数。

思路

完全是上题LCS的变形,不赘述。

class Solution:
    def maxUncrossedLines(self, nums1: List[int], nums2: List[int]) -> int:
        dp = [[0] * (len(nums2)+1) for _ in range(len(nums1)+1)]
        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
                else:
                    dp[i][j] = max(dp[i][j-1],dp[i-1][j])
                
        return dp[len(nums1)][len(nums2)]

53. 最大子数组和

给你一个整数数组 nums ,请你找出一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。
子数组是数组中的一个连续部分。

思路

dp[i] 是以索引i为结尾的最大和,它为

  • 之前的连续最大和加上自己
  • 自己重新开始记录

两者的最大值

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

392. 判断子序列

给定字符串 s 和 t ,判断 s 是否为 t 的子序列。
字符串的一个子序列是原始字符串删除一些(也可以不删除)字符而不改变剩余字符相对位置形成的新字符串。(例如,"ace"是"abcde"的一个子序列,而"aec"不是)。

思路

是LCS的变形,只要两个字符串的最长公共子序列的长度为子序列s的长度,说明s是t的子序列,否则则不是。

class Solution:
    def isSubsequence(self, s: str, t: str) -> bool:
        dp = [[0] * (len(t)+1) for _ in range(len(s)+1)]
        for i in range(1,len(s) + 1):
            for j in range(1,len(t) + 1):
                if s[i-1] == t[j-1]:
                    dp[i][j] = dp[i-1][j-1] + 1
                else:
                    dp[i][j] = max(dp[i][j-1],dp[i-1][j])
        return True if dp[len(s)][len(t)] == len(s) else False

标签:第九章,Part11,len,字符串,range,序列,动态,nums1,dp
From: https://www.cnblogs.com/haohaoscnblogs/p/18386512

相关文章

  • 第九章 动态规划Part10
    目录任务300.最长递增子序列思路674.最长连续递增序列思路718.最长重复子数组思路任务300.最长递增子序列子序列是由数组派生而来的序列,删除(或不删除)数组中的元素而不改变其余元素的顺序。例如,[3,6,2,7]是数组[0,3,1,6,2,2,7]的子序列思路dp[i]表示以索引i结尾的最......
  • 【零信任方案】持续安全风险评估与动态访问控制实现方案
    一、为什么做持续安全风险评估与动态访问控制二、实现方案思路三、详细实现方案原创网络个人修炼一、为什么要持续进行安全风险评估和动态的访问控制访问控制是比较常见的安全隔离技术,我们这里主要讲网络访问的访问控制,其他文件存储读取访问等其他访问也是类似。传统......
  • 算法-动态规划-完全背包
    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值可以放到方法的......