当前位置: 首页 > news >正文

代码随想录Day45 动态规划13 LeetCode T1143最长公共子序列 T1135 不相交的线 T53最大子数组和

LeetCode T1143 最长公共子序列

题目链接:1143. 最长公共子序列 - 力扣(LeetCode)

题目思路:

动规五部曲分析

1.确定dp数组的含义

这里dp数组的含义是结尾分别为i-1,j-1的text1和text2的最长公共子序列长度

至于为什么是i-1,j-1我之前已经说过了,这里再说一次,因为如果定义为i和j 的话就需要比较两个字符串的首字母分别是否相等来初始化dp[0][i]和dp[0][j],因为这样定义的话dp[0][j]和    dp[i][0]就没有含义,省去了初始化的部分

2.确定递推公式

dp[i][j]可以从dp[i-1][j-1],dp[i-1][j]和dp[i][j-1]三个推出来

当text1[i]和text2[j]相等时,就是dp[i-1][j-1]+1

当两者不相等时,就是剩下两者的最大值

3.初始化dp数组

无需初始化,原因上面说清楚了,而剩下的所有值都会被覆盖,所以无所谓

4.遍历顺序

从前向后,因为后面的数据是前面产生的

5.打印排错

题目代码:

class Solution {public int longestCommonSubsequence(String text1, String text2) {int dp[][] = new int[text1.length()+1][text2.length()+1];for(int i = 1;i<=text1.length();i++){char c = text1.charAt(i-1);for(int j = 1;j<=text2.length();j++){char c2 = text2.charAt(j-1);if(c == c2){dp[i][j] = dp[i-1][j-1]+1;}else{dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]);}}}return dp[text1.length()][text2.length()];}
}

LeetCode T1135 不相交的线

题目链接:1035. 不相交的线 - 力扣(LeetCode)

题目思路:

这里我们可以将这一题的思路转化一下,其实就和第一题的思路一模一样,题目要求两条对应的线不能相交,其实就是交代了有序性,这也满足了第一题的条件,求最长公共子序列,所以不做过多赘述.

题目代码:

class Solution {public int maxUncrossedLines(int[] nums1, int[] nums2) {int[][] dp = new int[nums1.length+1][nums2.length+1];int res = 0;for(int i = 1;i<=nums1.length;i++){for(int j = 1;j<=nums2.length;j++){if(nums1[i-1] == nums2[j-1]){dp[i][j] = dp[i-1][j-1]+1;}else{dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]);}}}return dp[nums1.length][nums2.length];}
}

LeetCode T53 最大子数组和

题目链接:53. 最大子数组和 - 力扣(LeetCode)

题目思路:

动规五部曲分析

1.确定dp数组的含义

这里dp数组的含义是i位置之前(包括i在内)最大连续子序列之和

这一题我们在之前也用过贪心的思路来求解,见文章

代码随想录 Day26 贪心 01 全集 LeetCode455 分发饼干 LeetCodeT346摆动序列 LeetCdoe T53 最大子数组和-CSDN博客

2.确定递推公式

dp[i][j]可以从前面一个推出,如果累计和小于当前的nums[i],就从nums[i]开始记录

3.初始化dp数组

dp[0] = nums[0];不能初始化为0,因为有一个元素的情况存在

4.遍历顺序

从前向后遍历即可

5.打印排错

注意:这题的结果不在结尾取,要定义一个res在赋值的时候顺便记录最大值

题目代码:

class Solution {public int maxSubArray(int[] nums) {int[] dp = new int[nums.length];dp[0] = nums[0];int res = dp[0];for(int i = 1;i<nums.length;i++){dp[i] = Math.max(dp[i-1]+nums[i],nums[i]);res = Math.max(res,dp[i]);}return res;}
}

相关文章:

代码随想录Day45 动态规划13 LeetCode T1143最长公共子序列 T1135 不相交的线 T53最大子数组和

LeetCode T1143 最长公共子序列 题目链接:1143. 最长公共子序列 - 力扣&#xff08;LeetCode&#xff09; 题目思路: 动规五部曲分析 1.确定dp数组的含义 这里dp数组的含义是结尾分别为i-1,j-1的text1和text2的最长公共子序列长度 至于为什么是i-1,j-1我之前已经说过了,这里再…...

写了个监控 ElasticSearch 进程异常的脚本!

服务器配置免密钥环境准备&#xff1a; 配置免密钥前&#xff0c;需要在服务器的 hosts 文件中配置目标主机名称与 IP 对应关系。 vim /etc/hosts IP1 hostname1 IP2 hostname2 ...... 将 mianmiyaojiaoben.zip 安装包解压在当前目录下 cd /usr/local/jiaoben unzip mianmi…...

第三篇 基于JSP 技术的网上购书系统—— 数据库系统设计(网上商城、仿淘宝、当当、亚马逊)

目录 1.逻辑关系设计 2.物理设计 2.1管理员表 2.2留言表 2.3会员登录表 2.4会员表 2.5订单表 2.6订单商品表 2.7产品表 2.8产品货架表 2.9收藏表 2.10类别表 2.11新闻表 数据库系统是用来保存数据的软件系统&#xff0c;当今比较流行的数据库系统&#xff0c;如 MS…...

电脑检测温度软件有哪些?

环境&#xff1a; Win10 专业版 问题描述&#xff1a; 电脑检测温度软件有哪些&#xff1f; 解决方案&#xff1a; 有很多电脑检测温度的软件可供选择&#xff0c;以下是一些常用的电脑温度监测工具&#xff1a; HWMonitor&#xff1a;一款免费的硬件监控软件&#xff0…...

设计模式 -- 单例模式(Singleton Pattern)

单例模式&#xff1a;最简单的设计模式之一。这种类型的设计模式属于创建型模式&#xff0c;它提供了一种创建对象的最佳方式。这种模式涉及到一个单一的类&#xff0c;该类负责创建自己的对象&#xff0c;同时确保只有单个对象被创建。这个类提供了一种访问其唯一的对象的方式…...

ubuntu给终端加代理服务器

ubuntu给终端加代理 访问google.com 是否可以访问通 curl https://www.google.com如果访问不通说明代理服务器没有配置好。 使用 gedit ~/.bashrc 打开网络配置 gedit ~/.bashrc找到文章的最后添加代理 export http_proxyhttp://127.0.0.1:7890 export https_proxyhttp://…...

centos 6.10 安装 readline 6.2.0

下载地址 解压文件 cd readline-6.2 ./configure -prefix /usr/local/readline-6.2 make && make install安装完成...

IDEA 2023搭建 SpringMVC +FreeMarker+JDBC

1.IDEA的版本&#xff0c;目前最新是2023&#xff0c;要选择旗舰版。笔者曾选择社区版&#xff0c;发现少了很多功能。只能重新安装。 2.安装好以后的第1件事&#xff0c;是设置Maven&#xff0c;并将下载地址改为淘定站&#xff0c;参照这篇一次包会——最新IDEA配置Maven指南…...

RabbitMQ传统数据持久化和Lazy queue的区别

问题引出&#xff1a; 在了解这个问题前我们需要一些前置知识&#xff1a; 关于MQ可靠性&#xff0c;在默认情况下&#xff0c;RabbitMQ会将接收到的信息保存在内存中以降低消息收发的延迟。这样会导致两个问题&#xff1a; 一旦MQ宕机&#xff0c;内存中的信息会丢失 内存空…...

docker部署lnmp环境

文章目录 前期准备&#xff1a;一、部署mysql1.1 获取 Mysql 5.7.22 镜像1.2 启动mysql容器 二、部署php2.1 获取php 7.2镜像2.2 启动php 容器2.3 php的扩展安装 三、部署nginx3.1 获取nginx:1.14镜像3.2 启动nginx容器3.3 编写nginx虚拟主机配置文件&#xff0c;使其支持php3.…...

数据结构 | 带头双向循环链表专题

数据结构 | 带头双向循环链表专题 前言 前面我们学了单链表&#xff0c;我们这次来看一个专题带头的双向循环链表~~ 文章目录 数据结构 | 带头双向循环链表专题前言带头双向循环链表的结构实现双向链表头文件的定义创建节点哨兵位初始化尾插尾删头插头删打印查找指定位置前插入…...

Redis使用Pipeline(管道)批量处理

Redis 批量处理 在开发中&#xff0c;有时需要对Redis 进行大批量的处理。 比如Redis批量查询多个Hash。如果是在for循环中逐个查询&#xff0c;那性能会很差。 这时&#xff0c;可以使用 Pipeline (管道)。 Pipeline (管道) Pipeline (管道) 可以一次性发送多条命令并在执…...

Linux中at命令添加一次性任务

1、工作原理 功能&#xff1a;在某个时间点&#xff0c;执行一次命令。 特点&#xff1a;任务是用户隔离的。 条件&#xff1a;必须要保证atd进程存在。 ps -ef |grep atd 原理&#xff1a;atd进程循环遍历队列里的任务&#xff0c;有任务&#xff0c;且到达执行时间&#xff…...

交换机基础知识之安全配置

交换机在网络基础设施中扮演着重要角色&#xff0c;它促进了设备之间数据包的流动。正因此&#xff0c;采取适当的安全措施来保护网络免受未经授权的访问和潜在攻击至关重要。本文将全面解读交换机基础安全配置知识&#xff0c;并提供实践方案&#xff0c;以保证安全的网络环境…...

Netty入门指南之Reactor模型

作者简介&#xff1a;☕️大家好&#xff0c;我是Aomsir&#xff0c;一个爱折腾的开发者&#xff01; 个人主页&#xff1a;Aomsir_Spring5应用专栏,Netty应用专栏,RPC应用专栏-CSDN博客 当前专栏&#xff1a;Netty应用专栏_Aomsir的博客-CSDN博客 文章目录 参考文献前言单线程…...

Ubuntu20.04软件安装顺序

目录 0.网卡驱动1. sogoupinyin2. terminator3.1zsh3.2升级Cmake&#xff08;有些后面的软件需要高版本Cmake&#xff09;4.显卡驱动(在cuda之前)5.CUDA与cudnn,TensorRT6.OpenCV(在ROS之前)6.1先安装各种依赖6.2安装Ceres-1.14.06.3安装Pangolin6.4安装Sophus6.5安装VTK6.5编译…...

适配器模式 ( Adapter Pattern )(6)

适配器模式 ( Adapter Pattern ) 适配器模式&#xff08;Adapter Pattern&#xff09;是作为两个不兼容的接口之间的桥梁 适配器模式涉及到一个单一的类&#xff0c;该类负责加入独立的或不兼容的接口功能 举个真实的例子&#xff0c;读卡器是作为内存卡和笔记本之间的适配器…...

JAVA G1垃圾收集器介绍

为解决CMS算法产生空间碎片和其它一系列的问题缺陷&#xff0c;HotSpot提供了另外一种垃圾回收策略&#xff0c;G1&#xff08;Garbage First&#xff09;算法&#xff0c;通过参数-XX:UseG1GC来启用&#xff0c;该算法在JDK 7u4版本被正式推出&#xff0c;官网对此描述如下&am…...

十方影视后期“领进门”,成长与成就还得靠自身

在这个充满视觉冲击的时代&#xff0c;影视后期制作已经成为了一种炙手可热的艺术形式。而在这个领域&#xff0c;Adobe After Effects&#xff08;AE&#xff09;这款软件无疑是王者之一。十方影视后期作为十方教育科技旗下的艺术设计学科&#xff0c;不仅培养了数万名优秀的后…...

Golang之火爆原因

引言 在计算机编程领域&#xff0c;有很多种编程语言可供选择。然而&#xff0c;近年来&#xff0c;Golang&#xff08;Go&#xff09;这门相对年轻的编程语言却越来越受欢迎&#xff0c;备受推崇。那么&#xff0c;为什么Golang如此火爆&#xff1f;本文将探讨Golang之火爆原…...

《Qt C++ 与 OpenCV:解锁视频播放程序设计的奥秘》

引言:探索视频播放程序设计之旅 在当今数字化时代,多媒体应用已渗透到我们生活的方方面面,从日常的视频娱乐到专业的视频监控、视频会议系统,视频播放程序作为多媒体应用的核心组成部分,扮演着至关重要的角色。无论是在个人电脑、移动设备还是智能电视等平台上,用户都期望…...

【HarmonyOS 5.0】DevEco Testing:鸿蒙应用质量保障的终极武器

——全方位测试解决方案与代码实战 一、工具定位与核心能力 DevEco Testing是HarmonyOS官方推出的​​一体化测试平台​​&#xff0c;覆盖应用全生命周期测试需求&#xff0c;主要提供五大核心能力&#xff1a; ​​测试类型​​​​检测目标​​​​关键指标​​功能体验基…...

《Playwright:微软的自动化测试工具详解》

Playwright 简介:声明内容来自网络&#xff0c;将内容拼接整理出来的文档 Playwright 是微软开发的自动化测试工具&#xff0c;支持 Chrome、Firefox、Safari 等主流浏览器&#xff0c;提供多语言 API&#xff08;Python、JavaScript、Java、.NET&#xff09;。它的特点包括&a…...

oracle与MySQL数据库之间数据同步的技术要点

Oracle与MySQL数据库之间的数据同步是一个涉及多个技术要点的复杂任务。由于Oracle和MySQL的架构差异&#xff0c;它们的数据同步要求既要保持数据的准确性和一致性&#xff0c;又要处理好性能问题。以下是一些主要的技术要点&#xff1a; 数据结构差异 数据类型差异&#xff…...

ElasticSearch搜索引擎之倒排索引及其底层算法

文章目录 一、搜索引擎1、什么是搜索引擎?2、搜索引擎的分类3、常用的搜索引擎4、搜索引擎的特点二、倒排索引1、简介2、为什么倒排索引不用B+树1.创建时间长,文件大。2.其次,树深,IO次数可怕。3.索引可能会失效。4.精准度差。三. 倒排索引四、算法1、Term Index的算法2、 …...

NFT模式:数字资产确权与链游经济系统构建

NFT模式&#xff1a;数字资产确权与链游经济系统构建 ——从技术架构到可持续生态的范式革命 一、确权技术革新&#xff1a;构建可信数字资产基石 1. 区块链底层架构的进化 跨链互操作协议&#xff1a;基于LayerZero协议实现以太坊、Solana等公链资产互通&#xff0c;通过零知…...

2023赣州旅游投资集团

单选题 1.“不登高山&#xff0c;不知天之高也&#xff1b;不临深溪&#xff0c;不知地之厚也。”这句话说明_____。 A、人的意识具有创造性 B、人的认识是独立于实践之外的 C、实践在认识过程中具有决定作用 D、人的一切知识都是从直接经验中获得的 参考答案: C 本题解…...

在Ubuntu24上采用Wine打开SourceInsight

1. 安装wine sudo apt install wine 2. 安装32位库支持,SourceInsight是32位程序 sudo dpkg --add-architecture i386 sudo apt update sudo apt install wine32:i386 3. 验证安装 wine --version 4. 安装必要的字体和库(解决显示问题) sudo apt install fonts-wqy…...

C++.OpenGL (20/64)混合(Blending)

混合(Blending) 透明效果核心原理 #mermaid-svg-SWG0UzVfJms7Sm3e {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-SWG0UzVfJms7Sm3e .error-icon{fill:#552222;}#mermaid-svg-SWG0UzVfJms7Sm3e .error-text{fill…...

C++ 设计模式 《小明的奶茶加料风波》

&#x1f468;‍&#x1f393; 模式名称&#xff1a;装饰器模式&#xff08;Decorator Pattern&#xff09; &#x1f466; 小明最近上线了校园奶茶配送功能&#xff0c;业务火爆&#xff0c;大家都在加料&#xff1a; 有的同学要加波霸 &#x1f7e4;&#xff0c;有的要加椰果…...