代码随想录算法训练营第五十六天 | 动态规划 part 14 | 1143.最长公共子序列、1035.不相交的线、53. 最大子序和(dp)
目录
- 1143.最长公共子序列
- 思路
- 代码
- 1035.不相交的线
- 思路
- 代码
- 53. 最大子序和(dp)
- 思路
- 代码
1143.最长公共子序列
Leetcode

思路
本题和718. 最长重复子数组 区别在于这里不要求是连续的了,但要有相对顺序,即:“ace” 是 “abcde” 的子序列,但 “aec” 不是 “abcde” 的子序列。
不是连续的话,具体写代码的区别体现在递推公式上,
if text1[i - 1] != text2[j - 1]: dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
从下图可以看出来可以有三个方向推导出dp[i][j]

举例推导dp数组
以输入:text1 = “abcde”, text2 = “ace” 为例,dp状态如图:

代码
class Solution:def longestCommonSubsequence(self, text1: str, text2: str) -> int:dp = [[0] * (len(text1) + 1) for _ in range(len(text2) + 1)]for i in range(1, len(text2) + 1):for j in range(1, len(text1) + 1):if text2[i - 1] == text1[j - 1]:dp[i][j] = dp[i - 1][j - 1] + 1else:dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])return dp[-1][-1]
- 时间复杂度:
O(n * m),其中 n 和 m 分别为 text1 和 text2 的长度 - 空间复杂度:
O(n * m)
1035.不相交的线
Leetcode

思路
此题和上题一模一样。
代码
class Solution:def maxUncrossedLines(self, nums1: List[int], nums2: List[int]) -> int:dp = [[0] * (len(nums1) + 1) for _ in range(len(nums2) + 1)]for i in range(1, len(nums2) + 1):for j in range(1, len(nums1) + 1):if nums2[i - 1] == nums1[j - 1]:dp[i][j] = dp[i - 1][j - 1] + 1else:dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])return dp[-1][-1]
53. 最大子序和(dp)
Leetcode

思路
- dp[i]:包括下标i(以nums[i]为结尾)的最大连续子序列和为dp[i]。
- 递推公式:
dp[i]只有两个方向可以推出来:dp[i - 1] + nums[i],即:nums[i]加入当前连续子序列和nums[i],即:从头开始计算当前连续子序列和
我一开始写成了dp[i] = max(dp[i], dp[i - 1] + nums[i]),那这就不对了,因为这样就会受到dp[i]初始化的影响。
- 初始化:dp[0] = nums[0],剩下的随意
- 遍历顺序从前往后
- 举例
以示例一为例,输入:nums = [-2,1,-3,4,-1,2,1,-5,4],对应的dp状态如下:

代码
class Solution:def maxSubArray(self, nums: List[int]) -> int:dp = [nums[0]] * len(nums)res = nums[0]for i in range(1, len(nums)):dp[i] = max(nums[i], dp[i - 1] + nums[i])res = max(res, dp[i])return res
- 时间复杂度:
O(n) - 空间复杂度:
O(n)
相关文章:
代码随想录算法训练营第五十六天 | 动态规划 part 14 | 1143.最长公共子序列、1035.不相交的线、53. 最大子序和(dp)
目录 1143.最长公共子序列思路代码 1035.不相交的线思路代码 53. 最大子序和(dp)思路代码 1143.最长公共子序列 Leetcode 思路 本题和718. 最长重复子数组 区别在于这里不要求是连续的了,但要有相对顺序,即:“ace” …...
【数据挖掘】2021年 Quiz 1-3 整理 带答案
目录 Quiz 1Quiz 2Quiz 3Quiz 1 Problem 1 (30%). Consider the training data shown below. Here, A A A and B B B</...
【软件设计师-中级——刷题记录6(纯干货)】
目录 管道——过滤器软件体系结构风格优点:计算机英语重点词汇:单元测试主要检查模块的以下5个特征:数据库之并发控制中的事务:并发产生的问题解决方案:封锁协议原型化开发方法: 每日一言:持续更新中... 个…...
微信小程序点单左右联动的效果实现
微信小程序点单左右联动的效果实现 原理解析: 点击左边标签会跳到右边相应位置:点击改变rightCur值,转跳相应位置滑动右边,左边标签会跳到相应的位置:监听并且设置每个右边元素的top和bottom,再判断当…...
Socket通信
优质博文IT-BLOG-CN 一、简介 Socket套接字:描述了计算机的IP地址和端口,运行在计算机中的程序之间采用socket进行数据通信。通信的两端都有socket,它是一个通道,数据在两个socket之间进行传输。socket把复杂的TCP/IP协议族隐藏在…...
TCP 如何保证有效传输及拥塞控制
TCP(传输控制协议)可以通过以下机制保证有效传输和拥塞控制: 确认机制:TCP使用确认机制来保证数据的有效传输。发送方在发送数据的同时还会发送一个确认请求,接收方收到数据后会回复确认响应。如果发送方没有收到确认响…...
PyQt5+Qt设计师初探
在上一篇文章中我们搭建好了PyQt5的开发环境,打铁到趁热我们基于搭建好的环境来简单实战一把 一:PyQt5包模块简介 PyQt5包括的主要模块如下。 QtCore模块——涵盖了包的核心的非GUI功能,此模块被用于处理程序中涉及的时间、文件、目录、数…...
rust cargo
一、cargo是什么 Cargo是Rust的构建工具和包管理器。 Cargo除了创建工程、构建工程、运行工程等功能,还具有下载依赖库、编译依赖等功能。 真正编写程序时,我们不直接用rustc,而是用cargo。 二、使用cargo (一)使用…...
CANoe.Diva生成测试用例
Diva目录 一、CANoe.Diva打开CDD文件二、导入CDD文件三、ECU Information四、时间参数设置五、选择是否测试功能寻址六、勾选需要测试服务项七、生成测试用例 一、CANoe.Diva打开CDD文件 CANoe.Diva可以通过导入cdd或odx文件,自动生成全面的测试用例。再在CANoe中导…...
openGauss学习笔记-89 openGauss 数据库管理-内存优化表MOT管理-内存表特性-使用MOT-MOT使用查询原生编译
文章目录 openGauss学习笔记-89 openGauss 数据库管理-内存优化表MOT管理-内存表特性-使用MOT-MOT使用查询原生编译89.1 查询编译:PREPARE语句89.2 运行命令89.3 轻量执行支持的查询89.4 轻量执行不支持的查询89.5 JIT存储过程89.6 MOT JIT诊断89.6.1 mot_jit_detai…...
python获取时间戳
使用 datetime 库获取时间。 获取当前时间: import datetime print(datetime.datetime.now()) . 后面的是微秒,也是一个时间单位,1秒1000000微秒。 转为时间戳: import datetimedate datetime.datetime.now() timestamp date…...
2023年山东省安全员C证证考试题库及山东省安全员C证试题解析
题库来源:安全生产模拟考试一点通公众号小程序 2023年山东省安全员C证证考试题库及山东省安全员C证试题解析是安全生产模拟考试一点通结合(安监局)特种作业人员操作证考试大纲和(质检局)特种设备作业人员上岗证考试大…...
Java中的Unicode字符编码与占用比特位解析
本文将详细介绍Java中Unicode字符编码与占用比特位的相关知识。我们将首先介绍Unicode字符集的基本概念,然后深入探讨Java中Unicode字符的编码方式以及占用比特位的特点。最后,我们将讨论一些特殊字符的编码情况,并给出一些在Java中处理Unico…...
分布式事务-TCC案例分析流程图
防止cancel方法在最后执行出现问题,用户收到提示已经退款成功但是由于cancel过慢或者出现问题(虽然最后会重试成功但是用户体验很差),可以做以下的业务sql模型优化(增加一个冻结金额)。...
究竟是什么样的讲解数组算法的博客让我写了三小时???
版本说明 当前版本号[20231004]。 版本修改说明20231004初版 目录 文章目录 版本说明目录二. 基础数据结构2.1 数组1) 概述2) 动态数组1)插入addlast 方法测试: addlast 方法 add 方法测试:add方法 addlast 方法与 add 方法合并版get 方法测试&#x…...
Day-05 CentOS7.5 安装docker
参考 : Install Docker Engine on CentOS | Docker DocsLearn how to install Docker Engine on CentOS. These instructions cover the different installation methods, how to uninstall, and next steps.https://docs.docker.com/engine/install/centos/ Doc…...
Makefile
目录 Makefile Makefile格式 Makefile函数:foreach和wildcard $(foreach var,list,text) $(wildcard pattern) 完善Makefile Makefile 在Linux中使用make工具来编译程序(特别是大程序),而make工具所执行的动作依赖于Makefil…...
c语言练习77:公因⼦的数⽬
公因⼦的数⽬ 题⽬描述: 给你两个正整数 a 和 b ,返回 a 和 b 的公因⼦的数⽬。 如果 x 可以同时整除 a 和 b ,则认为 x 是 a 和 b 的⼀个公因⼦ 。 • ⽰例 1: 输⼊:a 12, b 6 输出:4 解释&#…...
【C++】C++11——右值引用和移动语义、左值引用和右值引用、右值引用使用场景和意义、完美转发、新的类功能
文章目录 C115.右值引用和移动语义5.1左值引用和右值引用5.2左值引用与右值引用比较5.3右值引用使用场景和意义5.4右值引用引用左值及其一些更深入的使用场景分析5.5完美转发 6.新的类功能 C11 5.右值引用和移动语义 右值引用是C11引入的一个新特性,用于支持移动语义…...
Spring Boot的创建和使用(JavaEE进阶系列2)
目录 前言: 1.什么是Spring Boot?为什么要学习Spring Boot? 2.Spring Boot优点 3.创建Spring Boot项目 3.1准备工作 3.2Spring Boot创建 3.2.1通过idea的方式创建 3.2.2通过网页创建 4.Spring Boot中的配置文件 4.1Spring Boot配置…...
LBE-LEX系列工业语音播放器|预警播报器|喇叭蜂鸣器的上位机配置操作说明
LBE-LEX系列工业语音播放器|预警播报器|喇叭蜂鸣器专为工业环境精心打造,完美适配AGV和无人叉车。同时,集成以太网与语音合成技术,为各类高级系统(如MES、调度系统、库位管理、立库等)提供高效便捷的语音交互体验。 L…...
C++_核心编程_多态案例二-制作饮品
#include <iostream> #include <string> using namespace std;/*制作饮品的大致流程为:煮水 - 冲泡 - 倒入杯中 - 加入辅料 利用多态技术实现本案例,提供抽象制作饮品基类,提供子类制作咖啡和茶叶*//*基类*/ class AbstractDr…...
12.找到字符串中所有字母异位词
🧠 题目解析 题目描述: 给定两个字符串 s 和 p,找出 s 中所有 p 的字母异位词的起始索引。 返回的答案以数组形式表示。 字母异位词定义: 若两个字符串包含的字符种类和出现次数完全相同,顺序无所谓,则互为…...
【JavaSE】绘图与事件入门学习笔记
-Java绘图坐标体系 坐标体系-介绍 坐标原点位于左上角,以像素为单位。 在Java坐标系中,第一个是x坐标,表示当前位置为水平方向,距离坐标原点x个像素;第二个是y坐标,表示当前位置为垂直方向,距离坐标原点y个像素。 坐标体系-像素 …...
智能仓储的未来:自动化、AI与数据分析如何重塑物流中心
当仓库学会“思考”,物流的终极形态正在诞生 想象这样的场景: 凌晨3点,某物流中心灯火通明却空无一人。AGV机器人集群根据实时订单动态规划路径;AI视觉系统在0.1秒内扫描包裹信息;数字孪生平台正模拟次日峰值流量压力…...
Java面试专项一-准备篇
一、企业简历筛选规则 一般企业的简历筛选流程:首先由HR先筛选一部分简历后,在将简历给到对应的项目负责人后再进行下一步的操作。 HR如何筛选简历 例如:Boss直聘(招聘方平台) 直接按照条件进行筛选 例如:…...
Android 之 kotlin 语言学习笔记三(Kotlin-Java 互操作)
参考官方文档:https://developer.android.google.cn/kotlin/interop?hlzh-cn 一、Java(供 Kotlin 使用) 1、不得使用硬关键字 不要使用 Kotlin 的任何硬关键字作为方法的名称 或字段。允许使用 Kotlin 的软关键字、修饰符关键字和特殊标识…...
智能分布式爬虫的数据处理流水线优化:基于深度强化学习的数据质量控制
在数字化浪潮席卷全球的今天,数据已成为企业和研究机构的核心资产。智能分布式爬虫作为高效的数据采集工具,在大规模数据获取中发挥着关键作用。然而,传统的数据处理流水线在面对复杂多变的网络环境和海量异构数据时,常出现数据质…...
Java线上CPU飙高问题排查全指南
一、引言 在Java应用的线上运行环境中,CPU飙高是一个常见且棘手的性能问题。当系统出现CPU飙高时,通常会导致应用响应缓慢,甚至服务不可用,严重影响用户体验和业务运行。因此,掌握一套科学有效的CPU飙高问题排查方法&…...
Java 二维码
Java 二维码 **技术:**谷歌 ZXing 实现 首先添加依赖 <!-- 二维码依赖 --><dependency><groupId>com.google.zxing</groupId><artifactId>core</artifactId><version>3.5.1</version></dependency><de…...
