动态规划-两个数组的dp问题——718.最长重复子数组

1.题目解析

题目来源

718.最长重复子数组——力扣

测试用例 

2.算法原理

1.状态表示

子数组问题不能像子序列问题使用两个区间来表示状态,因为子数组一定是连续的,因此在填第i个位置就需要用到第i-1个位置的值,那么不妨以某个位置为结尾来设置dp表,即

dp[i][j]:以s1的第i个位置为结尾与以s2的第j个位置为结尾的字符串中最长公共子数组的长度

2.状态转移方程

这里需要借助最后位置字符是否相等来判断,相等则找到前一个位置的dp值后对最长公共组数组的长度+1,也就是dp[i-1][j-1]+1,反之不相等则一定不能构成最长公共子数组,直接将该位置dp表的值赋值为0即可

3.初始化

开辟虚拟位置,但是虚拟位置节点为0,于是无需初始化

4.填表顺序

从上到下,每一行从左到右

5.返回值 

返回dp表中的最大值就是最长公共子序列的长度

3.实战代码

代码解析

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

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

软件工程 软考

开发大型软件系统适用螺旋模型或者RUP模型 螺旋模型强调了风险分析&#xff0c;特别适用于庞大而复杂的、高风险的管理信息系统的开发。喷泉模型是一种以用户需求为动力&#xff0c;以对象为为驱动的模型&#xff0c;主要用于描述面向对象的软件开发过程。该模型的各个阶段没有…

【日志】392.判断子序列

2024.11.8 【力扣刷题】 392. 判断子序列 - 力扣&#xff08;LeetCode&#xff09;https://leetcode.cn/problems/is-subsequence/?envTypestudy-plan-v2&envIdtop-interview-150 整个题从一开始就是打算从双指针的思想往下走的。但是&#xff0c;我设置了四个变量sLeft…

高校宿舍信息管理系统小程序

作者主页&#xff1a;编程千纸鹤 作者简介&#xff1a;Java领域优质创作者、CSDN博客专家 、CSDN内容合伙人、掘金特邀作者、阿里云博客专家、51CTO特邀作者、多年架构师设计经验、多年校企合作经验&#xff0c;被多个学校常年聘为校外企业导师&#xff0c;指导学生毕业设计并参…

【含开题报告+文档+源码】基于SpringBoot的智慧养老医护管理系统

开题报告 随着社会老龄化趋势的不断加深&#xff0c;我国老年人口逐年增长&#xff0c;对养老服务的需求愈发迫切。然而&#xff0c;传统的养老服务模式存在许多不足&#xff0c;如信息孤岛、护理不精准等问题&#xff0c;迫切需要一种创新性的解决方案以提升养老服务的质量和…

【双十一特惠】腾讯云省钱攻略:如何智取云计算资源

前言 双十一不仅是购物的狂欢节&#xff0c;对于云计算用户来说&#xff0c;更是一个节省成本的绝佳时机。腾讯云&#xff0c;作为国内领先的云计算服务商&#xff0c;每年双十一都会推出一系列优惠活动。本文将为您揭开如何在这个购物节中&#xff0c;最大化利用腾讯云的优惠…

IEEE 1588:电信网络的精确时间协议 (PTP)

IEEE 1588&#xff1a;电信网络的精确时间协议 IEEE 1588 PTP 概述PTP 协议特征同步类型IEEE 1588 PTP 角色IEEE 1588 PTP 的工作原理PTP 设备类型PTP 消息类型事件消息一般信息 PTP 时钟类规范PTP 配置文件 https://www.techplayon.com/ieee-1588-precision-time-protocol-ptp…

昇思大模型平台打卡体验活动:基于MindSpore实现GPT1影评分类

如果你对MindSpore感兴趣&#xff0c;可以关注昇思MindSpore社区 大模型平台 平台说明 昇思大模型平台旨在为AI学习者和开发者提供在线学习的项目、模型、大模型体验和数据集的平台。我们也添加了各领域的经典数据集来帮助学习者解决AI学习过程中的一系列难题&#xff0c; 如…

在IDEA中使用Git

一、准备工作 这里我们使用 Gitee 做例子&#xff0c;使用 SSH 协议。看这个文章前最好看一下《》这个文章&#xff0c;了解一下 SSH。 1、生成秘钥对 首先要到 ~/.ssh 目录下进行操作&#xff0c;因为生成的公钥和私钥一般放在这个目录下&#xff0c;Windows 就是在用户目…

Linux下通过sqlplus连Oracle提示字符是乱码▒▒▒[

先参考https://www.cnblogs.com/wrencai/articles/4374451.html 理解下Oracle编码字符集的概念 如下图,刚开始连上是软吗▒▒▒[ 执行export NLS_LANGJAPANESE_JAPAN.AL32UTF8 (这个仅在当前会话起作用)如果好了,说明字符集是这个,不行在尝试别的字符集 如果要永久设置 vim …

Flyweight(享元)

1)意图 运用共享技术有效地支持大量细粒度的对象。 2)结构 享元模式的结构如图 7-36 所示。 其中: Flyweight 描述一个接口&#xff0c;通过这个接口 Flyweight 可以接受并作用于外部状态 ConcreteFlyweight 实现 Flyweight 接口&#xff0c;并为内部状态(如果有)增加存储空…

微信小程序中使用离线版阿里云矢量图标

前言 阿里矢量图库提供的在线链接服务仅供平台体验和调试使用&#xff0c;平台不承诺服务的稳定性&#xff0c;企业客户需下载字体包自行发布使用并做好备份。 1.下载图标 将阿里矢量图库的图标先下载下来 解压如下 2.转换格式 贴一个地址用于转换格式&#xff1a;Onlin…

大数据之多级缓存方案

多级缓存介绍&#xff1f;多级缓存优缺点&#xff0c;应用场景&#xff1f;多级缓存架构&#xff1f; 多级缓存介绍 多级缓存方案是一种优化手段&#xff0c;通过在多个级别上存储数据来提高应用程序的性能和响应速度。以下是对多级缓存方案的详细解析&#xff1a; 一、多级缓…

jupyter notebook启动和单元格cell

【注意&#xff01;&#xff01;&#xff01;】 本章主要讲解数据分析、挖掘入门及进阶知识 - 通过多篇文章【文字案例】的形式系统化进行描述 数据分析专栏&#xff1a;https://blog.csdn.net/2201_75422674/category_12827743.html - 大家喜欢可以订阅一下&#xff0c;不收费…

街道网格领域的数据大屏,在社区治理方面大显身手。

街道网格领域的数据大屏在社区治理中发挥着重要作用。它可以直观地展示社区的人口分布、治安状况、环境问题等各类信息。 通过实时更新的数据&#xff0c;社区工作人员能够及时掌握动态变化&#xff0c;迅速做出决策。色彩鲜明的图表和图形让复杂的数据一目了然&#xff0c;方…

14、NAT和桥接区别

一、NAT模式 NAT相当于是局域网中的局域网&#xff0c;把192.168.21.1当作外网ip&#xff0c;重新划分了一个网关&#xff08;192.168.33.x&#xff09; 二、桥接模式 网桥只是把网络桥接起来&#xff0c;还是原来的网关&#xff08;192.168.21.x&#xff09;&#xff0c;虚拟机…

k8s 处理namespace删除一直处于Terminating —— 筑梦之路

问题现象 k8s集群要清理某个名空间&#xff0c;把该名空间下的资源全部删除后&#xff0c;删除名空间&#xff0c;一直处于Terminating状态&#xff0c;无法完全清理掉。 如何处理 为什么要记录下这个处理的步骤&#xff0c;经过查询资料&#xff0c;网上也有各种各样的方法&…

鸿蒙多线程开发——Worker多线程

1、概 述 1.1、基本介绍 Worker主要作用是为应用程序提供一个多线程的运行环境&#xff0c;可满足应用程序在执行过程中与主线程分离&#xff0c;在后台线程中运行一个脚本进行耗时操作&#xff0c;极大避免类似于计算密集型或高延迟的任务阻塞主线程的运行。 创建Worker的线…

Python实现SSA智能麻雀搜索算法优化BP神经网络回归模型(优化权重和阈值)项目实战

说明&#xff1a;这是一个机器学习实战项目&#xff08;附带数据代码文档视频讲解&#xff09;&#xff0c;如需数据代码文档视频讲解可以直接到文章最后关注获取。 1.项目背景 随着人工智能技术的发展&#xff0c;机器学习算法在各个领域的应用越来越广泛。其中&#xff0c;神…

qt QListView详解

1、概述 QListView 是 Qt 框架中的一个视图类&#xff0c;用于展示模型中的数据。它基于 QAbstractItemView&#xff0c;支持多种视图模式&#xff0c;如列表视图&#xff08;List View&#xff09;、图标视图&#xff08;Icon View&#xff09;等。QListView 是模型/视图框架…

【MySQL】数据库整合攻略 :表操作技巧与详解

前言&#xff1a;本节内容讲述表的操作&#xff0c; 对表结构的操作。 是对表结构中的字段的增删查改以及表本身的创建以及删除。 ps&#xff1a;本节内容本节内容适合安装了MySQL的友友们进行观看&#xff0c; 实操更有利于记住哦。 目录 创建表 查看表结构 修改表结构 …