自学动态规划——最长重复子数组(子序列问题)

2024-06-01 05:36

本文主要是介绍自学动态规划——最长重复子数组(子序列问题),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

最长重复子数组

718. 最长重复子数组 - 力扣(LeetCode)

第一次接触,确实会有些懵,但是看了题解,仔细想想,确实是这么回事。要点如下:

  1. dp数组含义——dp[i][j]表示当num1取i个,nums2取j个的时候,其最长重复子数组的长度
  2. 递推公式——if(nums1[i-1]==nums2[j-1]) dp[i][j]=dp[i-1][j-1]+1;表示,如果当前长度下对应的最后一个值匹配上了,那么当前(i,j)的最长重复子数组的长度应该是之前两个数组退格1个时候的长度+1
  3. 初始化——当i==0 || j==0的时候,相当于一个数组为空,那么是绝对无法匹配的,即初始化为0。这也是为什么从1开始遍历,因为从0开始无意义,还需要额外加个判断,让她为0,还不如从一开始就让他为0

AC:

int findLength(vector<int>& nums1, vector<int>& nums2) {//只用1维实在很难想出来应该怎么做,但是如果开二维就不一样了int n1=nums1.size(),n2=nums2.size();vector<vector<int>>dp(n1+1,vector<int>(n2+1,0));    //dp[i][j] 表示当取num1长度i,num2长度j的时候,对应的最长重复子数组长度//初始化:i或j为0,那一定没有子数组,所以保持为0即可int ans=0;for(int i=1;i<=n1;i++){for(int j=1;j<=n2;j++){if(nums1[i-1]==nums2[j-1])  //因为ij表示的长度,所以定位到具体值的时候需要-1dp[i][j]=dp[i-1][j-1]+1;    //当前长度应该是两者退格1个前的基础上+1ans=max(ans,dp[i][j]);  //记录最值}}return ans;}

这篇关于自学动态规划——最长重复子数组(子序列问题)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1020118

相关文章

Flask解决指定端口无法生效问题

《Flask解决指定端口无法生效问题》文章讲述了在使用PyCharm开发Flask应用时,启动地址与手动指定的IP端口不一致的问题,通过修改PyCharm的运行配置,将Flask项目的运行模式从Fla... 目录android问题重现解决方案问题重现手动指定的IP端口是app.run(host='0.0.

Seata之分布式事务问题及解决方案

《Seata之分布式事务问题及解决方案》:本文主要介绍Seata之分布式事务问题及解决方案,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Seata–分布式事务解决方案简介同类产品对比环境搭建1.微服务2.SQL3.seata-server4.微服务配置事务模式1

mysql关联查询速度慢的问题及解决

《mysql关联查询速度慢的问题及解决》:本文主要介绍mysql关联查询速度慢的问题及解决方案,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录mysql关联查询速度慢1. 记录原因1.1 在一次线上的服务中1.2 最终发现2. 解决方案3. 具体操作总结mysql

一文教你解决Python不支持中文路径的问题

《一文教你解决Python不支持中文路径的问题》Python是一种广泛使用的高级编程语言,然而在处理包含中文字符的文件路径时,Python有时会表现出一些不友好的行为,下面小编就来为大家介绍一下具体的... 目录问题背景解决方案1. 设置正确的文件编码2. 使用pathlib模块3. 转换路径为Unicod

Spring MVC跨域问题及解决

《SpringMVC跨域问题及解决》:本文主要介绍SpringMVC跨域问题及解决方案,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录跨域问题不同的域同源策略解决方法1.CORS2.jsONP3.局部解决方案4.全局解决方法总结跨域问题不同的域协议、域名、端口

Java中数组转换为列表的两种实现方式(超简单)

《Java中数组转换为列表的两种实现方式(超简单)》本文介绍了在Java中将数组转换为列表的两种常见方法使用Arrays.asList和Java8的StreamAPI,Arrays.asList方法简... 目录1. 使用Java Collections框架(Arrays.asList)1.1 示例代码1.

基于Canvas的Html5多时区动态时钟实战代码

《基于Canvas的Html5多时区动态时钟实战代码》:本文主要介绍了如何使用Canvas在HTML5上实现一个多时区动态时钟的web展示,通过Canvas的API,可以绘制出6个不同城市的时钟,并且这些时钟可以动态转动,每个时钟上都会标注出对应的24小时制时间,详细内容请阅读本文,希望能对你有所帮助...

SpringBoot自定义注解如何解决公共字段填充问题

《SpringBoot自定义注解如何解决公共字段填充问题》本文介绍了在系统开发中,如何使用AOP切面编程实现公共字段自动填充的功能,从而简化代码,通过自定义注解和切面类,可以统一处理创建时间和修改时间... 目录1.1 问题分析1.2 实现思路1.3 代码开发1.3.1 步骤一1.3.2 步骤二1.3.3

基于.NET编写工具类解决JSON乱码问题

《基于.NET编写工具类解决JSON乱码问题》在开发过程中,我们经常会遇到JSON数据处理的问题,尤其是在数据传输和解析过程中,很容易出现编码错误导致的乱码问题,下面我们就来编写一个.NET工具类来解... 目录问题背景核心原理工具类实现使用示例总结在开发过程中,我们经常会遇到jsON数据处理的问题,尤其是

Vue中动态权限到按钮的完整实现方案详解

《Vue中动态权限到按钮的完整实现方案详解》这篇文章主要为大家详细介绍了Vue如何在现有方案的基础上加入对路由的增、删、改、查权限控制,感兴趣的小伙伴可以跟随小编一起学习一下... 目录一、数据库设计扩展1.1 修改路由表(routes)1.2 修改角色与路由权限表(role_routes)二、后端接口设计