非科班菜鸡算法学习记录 | 代码随想录算法训练营第53天|| 1143.最长公共子序列 1035.不相交的线 53. 最大子序和 动态规划


1143. 最长公共子序列

知识点:动规
状态:不会
思路:

用dpij表示两个串中到i-1和j-1个字符结束的最长公共子序列长度(不用特殊初始化)

class Solution {
public:int longestCommonSubsequence(string text1, string text2) {vector<vector<int>> dp(text1.size() + 1, vector<int>(text2.size() + 1, 0));for (int i = 1; i <= text1.size(); i++) {for (int j = 1; j <= text2.size(); j++) {if (text1[i - 1] == text2[j - 1]) {dp[i][j] = dp[i - 1][j - 1] + 1;} else {dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);}}}return dp[text1.size()][text2.size()];}
};


1035. 不相交的线

知识点:动规
状态:不会
思路:

本质上就是找最长公共子序列,跟上题一样

class Solution {
public:int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2) {vector<vector<int>> dp(nums1.size() +1, vector<int>(nums2.size() +1, 0));for(int i = 1; i <= nums1.size(); i++) {for(int j = 1; j <= nums2.size();j++) {if(nums1[i-1] == nums2[j-1]) {dp[i][j] = dp[i-1][j-1] + 1;}else dp[i][j] = max(dp[i-1][j], dp[i][j-1]);}}return dp[nums1.size()][nums2.size()];}
};


53. 最大子数组和
知识点:动规
状态:不会
思路:

包括下标i之前的最大连续子序列和为dp[i]。

所以取决于加上i位置数的和或者重新开始算这个数的最大值

class Solution {
public:int maxSubArray(vector<int>& nums) {vector<int > dp(nums.size(),0);int sum = 0;dp[0] = nums[0];int res = dp[0];for(int i = 1;i< nums.size();i++){dp[i] = max(dp[i-1] + nums[i], nums[i]);res = max(res,dp[i]);}return res;}
};

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/117792.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Web of Science批量导出

目录 如何用Web of Science检索学术信息问题批量导出 Web of Science检索结果 如何用Web of Science检索学术信息 进入 Web of Science 检索页面&#xff1a; https://www.webofscience.com/wos/woscc/basic-search 根据需求填写过滤条件&#xff0c;点击 search 进入搜索详…

C# char曲线控件

一、char曲线显示随机数数据 using System; using System.Collections.Generic; using System.ComponentModel; using System.Data; using System.Drawing; using System.Linq; using System.Runtime.InteropServices; using System.Text; using System.Threading; using Syst…

完全平方数

题目链接 完全平方数 题目描述 注意点 返回 和为 n 的完全平方数的最少数量 解答思路 初始想到使用动态规划&#xff0c;后续数字的完全平方数可以由前面数字的完全平方数求得&#xff0c;对于任意数字&#xff0c;可以计算其减去从1…i之间&#xff08;保证做减操作后的值…

【操作系统】一文快速入门,很适合JAVA后端看

作者简介&#xff1a; 目录 1.概述 2.CPU管理 3.内存管理 4.IO管理 1.概述 操作系统可以看作一个计算机的管理系统&#xff0c;对计算机的硬件资源提供了一套完整的管理解决方案。计算机的硬件组成有五大模块&#xff1a;运算器、控制器、存储器、输入设备、输出设备。操作…

Kubernetes技术--k8s核心技术 Secret

1.概述 Secret 解决了密码、token、密钥等敏感数据的配置问题,而不需要把这些敏感数据暴露到镜像或者 Pod Spec中。Secret可以以 Volume 或者环境变量的方式使用。 作用 加密数据存储在/etc中,使得pod容器以挂载volume方式进行访问。在进行的数据存储中是以base64加密的方式…

SQL 语句学习总结:

1. 四范式&&范式好处&#xff1a; 数据库范式是数据表设计的规范&#xff0c;在范式规范下&#xff0c;数据库里每个表存储的重复数据降到最少&#xff08;这有助于数据的一致性维护&#xff09;&#xff0c;同时在数据库范式下&#xff0c;表和表之间不再有很强的数据…

服务器数据恢复-vmware ESXI虚拟机数据恢复案例

服务器数据恢复环境&#xff1a; 从物理机迁移一台虚拟机到ESXI&#xff0c;迁移后做了一个快照。该虚拟机上部署了一个SQLServer数据库&#xff0c;存放了5年左右的数据。ESXI上有数十台虚拟机&#xff0c;EXSI连接了一台EVA存储&#xff0c;所有的虚拟机都在EVA存储上。 服务…

【综述】跨模态可信感知

文章目录 跨模态可信感知综述摘要引言跨协议通信模式PCP网络架构 跨模态可信感知跨模态可信感知的概念跨模态可信感知的热点研究场景目前存在的挑战可能改进的方案 参考文献 跨模态可信感知综述 摘要 随着人工智能相关理论和技术的崛起&#xff0c;通信和感知领域的研究引入了…

Linux系统下的zabbix监控平台(单机安装服务)

目录 一、zabbix的基本概述 二、zabbix构成 1.server 2.web页面 3.数据库 4.proxy 5.Agent 三、监控对象 四、zabbix的日常术语 1.主机(host) 2.主机组(host group) 3.监控项(item) 4.触发器(trigger) 5.事件&#xff08;event&#xff09; 6.动作&#xff08;a…

Aspose导出word使用记录

背景&#xff1a;Aspose系列的控件&#xff0c;功能实现都比较强大&#xff0c;可以实现多样化的报表设计及输出。 通过这次业务机会&#xff0c;锂宝碳审核中业务功需要实现Word文档表格的动态导出功能&#xff0c;因此学习了相关内容&#xff0c;在学习和参考了官方API文档的…

PSP - 蛋白质结构预测 OpenFold Multimer 训练模型的数据加载

欢迎关注我的CSDN&#xff1a;https://spike.blog.csdn.net/ 本文地址&#xff1a;https://spike.blog.csdn.net/article/details/132597659 OpenFold Multimer 是基于深度学习的方法&#xff0c;预测蛋白质的多聚体结构和相互作用。利用大规模的蛋白质序列和结构数据&#xff…

数据结构|栈和队列以及实现

栈和队列 一、栈1.1栈的概念及结构1.2栈的实现 二、队列2.1队列的概念及结构2.2队列的实现 一、栈 1.1栈的概念及结构 栈&#xff1a;一种特殊的线性表&#xff0c;其只允许在固定的一端进行插入和删除元素操作。进行数据插入和数据删除的一端称为栈顶&#xff0c;另一端称为栈…

vue的第2篇 开发环境vscode的安装以及创建项目空间

一 环境的搭建 1.1常见前端开发ide 1.2 安装vs.code 1.下载地址&#xff1a;Visual Studio Code - Code Editing. Redefined 2.进行安装 1.2.1 vscode的中文插件安装 1.在搜索框输入“chinese” 2.安装完成重启&#xff0c;如下变成中文 1.2.2 修改工作区的颜色 选中[浅色]…

HBuilderX修改manifest.json设置,解决跨域问题(CORS、Cross-Origin)

搭建一个前台uniapp&#xff0c;后台springboot的开发环境时&#xff0c;遇到了跨域问题。 console提示错误信息&#xff1a; Access to XMLHttpRequest at http://10.0.180.203/api/cms/getAdList?apId1 from origin http://localhost:8080 has been blocked by CORS policy…

微服务--Gatway:网关

routes: - id:order_route(路由唯一 标识&#xff0c;路由到order) uri&#xff1a;http://localhost:8020 #需要转发的地址 #断言规则&#xff08;用于路由规则的匹配&#xff09; predicates: -path/order-serv/** -pathlb://order-service # lb: 使用nacos中的本地…

随机森林算法

介绍 随机森林是一种基于集成学习的有监督机器学习算法。随机森林是包含多个决策树的分类器&#xff0c;一般输出的类别是由决策树的众数决定。随机森林也可以用于常见的回归拟合。随机森林主要是运用了两种思想。具体如下所示。 Breimans的Bootstrap aggregatingHo的random …

操作系统清华同步笔记:定义概述+计算机内存和硬盘布局+启动流程顺序+中断、异常和系统调用

定义概述 从用户角度来看&#xff0c;操作系统是一个控制软件&#xff0c;用以管理应用程序&#xff0c;为应用程序提供服务&#xff0c;杀死应用程序等。从内部文件角度来看&#xff0c;操作系统是一个资源管理器&#xff0c;用以管理外设&#xff0c;分配资源。层次结构&…

MySQL内容及原理记录

原理篇 架构、索引、事务、锁、日志、性能调优 高可用 读写分离、分库分表、分布式ID、高可用、分布式数据库、分布式事务、分布式锁 架构 1 执行一条 SQL 查询语句&#xff0c;期间发生了什么&#xff1f; &#xff08;1&#xff09;连接器&#xff1a;客户端通过连接器…

uniapp 支持图片放大

<view class"list" v-for"(item, index) in urls" :key"index"><image :src"item" click"viewImg(item, index)" disabled></image></view> js // 预览大图 viewImg(data, index) {uni.previewImag…

【Three.js + Vue 构建三维地球-Part One】

Three.js Vue 构建三维地球-Part One Vue 初始化部分Vue-cli 安装初始化 Vue 项目调整目录结构 Three.js 简介Three.js 安装与开始使用 实习的第一个任务是完成一个三维地球的首屏搭建&#xff0c;看了很多的案例&#xff0c;也尝试了用 Echarts 3D地球的模型进行构建&#xf…