718 最长重复子数组- 动态规划

题目描述:
给两个整数数组 A 和 B ,返回两个数组中公共的、长度最长的子数组的长度。

示例 1:
输入:
A: [1,2,3,2,1]
B: [3,2,1,4,7]
输出: 3
解释:
长度最长的公共子数组是 [3, 2, 1]。

说明:
1 <= len(A), len(B) <= 1000
0 <= A[i], B[i] < 100

方法一 动态规划
主要思路:
(1)使用二维的动态数组,dp[ i ] [ j ]表示第一个数组的第 i 个元素和第二个数组的第 j 个元素进行比较,若A[ i]==B[ j ],则表示此时的这两个元素处在重复的子数组之中,则 dp[ i ][ j ]=dp[ i-1 ][ j-1 ]+1,否则既为0;
(2)使用一个中间变量保存这个比较过程中最大的dp[ i ][ j ];

class Solution {
public:
    int findLength(vector<int>& A, vector<int>& B) {
    	//处理特殊情形
        if(A.empty()||B.empty())
            return 0;
        int rows=A.size();
        int cols=B.size();
        vector<vector<int>> dp(rows,vector<int>(cols,0));
        int res=0;
        //处理第一列的初始值,既使用B的第零个元素和A的所有元素比较
      for(int i=0;i<rows;++i){
            if(B[0]==A[i]){
                dp[i][0]=1;
                res=1;
            }        
        }
        //处理第一行的初始值,既使用A的第零个元素和B的所有元素比较
        for(int i=1;i<cols;++i){
            if(A[0]==B[i]){
                dp[0][i]=1;  
                res=1;
            }      
        }     
        //比较A的第i个元素和B的第j 个元素
        for(int i=1;i<rows;++i){
            for(int j=1;j<cols;++j){
                if(A[i]==B[j]){
                    dp[i][j]=dp[i-1][j-1]+1;
                     res=max(res,dp[i][j]);//保留当前的最长的重复子数组的长度
                }
            }
        }
        return res;
    }
};

热门文章

暂无图片
编程学习 ·

用Python读取pg数据库,准确统计每一张表的数据量,输出中英文表名和数据量

1 前言 在我们工作中,有时候老板关系我们手上到底有多少数据,每一张表中到底有多少数据量,整个库又有多少数据量?要给他一个准确的数据,给出一张详细清单。 在网上遇到的一种做法是使用navicat写SQL语句统计pg_class里面的reltuples这个列数据,但是发现这个数据有很大偏…
暂无图片
编程学习 ·

[UML] 类图之间的关系 | 4.接口与实现关系

[UML] 类图之间的关系 | 4.接口与实现关系 4.接口与实现关系接口之间也可以有与类之间关系类似的继承关系和依赖关系接口和类之间存在一种实现(Realization)关系,在这种关系中,类实现了接口,类中的操作实现了接口中声明的操作在UML中,类与接口之间的实现关系用带空心三角形…
暂无图片
编程学习 ·

树莓派4B介绍及其系统安装 入门教程(一)

树莓派4B介绍及其系统安装 入门教程(一)树莓派介绍系统下载安装连接外设启动后续计划入门进阶扩展参考资料 树莓派介绍 树莓派介绍可以参考链接: 树莓派介绍。里面介绍的很详细了,这里就不重复讲了,也可以去树莓派官方网站下载它的参数资料,里面也有很多利用树莓派设计制作…
暂无图片
编程学习 ·

【论文阅读报告】Visualizing and Understanding Convolutional Networks

背景 众所周知,卷积神经网络在图像处理方面表现突出,但是在很多情况下,我们在调神经网络的参数时只是依靠运气,并不知道自己对参数和网络结构的调整会影响神经网络的哪一部分。因此这篇文献的目的就是让我们通过一种可视化的方法来了解卷积神经网络如何工作,以及每一层的特…
暂无图片
编程学习 ·

java学习基础:Math类

记录学习java路程将与风雨相伴!!! Math类(数学类) 算术计算 Math.sqrt():计算平方根 Math.cbrt():计算立方根 Math.pow(a,b):计算a的b次方 Math.max(,):计算最大值 Math.min(,):计算最小值 Math.abs():取绝对值 进位 Math.ceil():天花板的意思,就…
暂无图片
编程学习 ·

SQL存储过程

什么是存储过程,如何创建一个存储过程 * Stored Procedure * 存储过程=SQL语句+流控制语句定义存储过程定义 create procedure 存储过程名称(【参数列表】) begin 需要执行的语句 end. 创建CREATE PROCEDURE `get_hero_scores`( OUT max_max_hp FLOAT, OUT min_max_mp FLO…
暂无图片
编程学习 ·

Fiddler(二)数据信息分析

抓包是Fiddler的最基本的应用,以本博客为例,启动Fiddler之后,在浏览器中输入http://blog.csdn.net/ohmygirl 键入回车之后,在Fiddler的web session界面捕获到的HTTP请求如下图所示:#号列中的图标,每种图标代表不同的相应类型,具体的类型包括:另外,注意请求的host字段。…
暂无图片
编程学习 ·

STM32CubeIDE TFT-LCD显示

随言:TFT-LCD的8080并口时序可以与ST的FSMC总线上操作SRAM的时序类似。故把TFT-LCD挂在SRAM上就能想操作SRAM一样操作TFT-LCD显示了。主要是STM32CubeIDE的时序图形配置。剩下的就是移植LCD显示厂商的驱动和寄存器设置,因为这部分设置太多了,自己看手册设置非常繁琐。重要是…
暂无图片
编程学习 ·

CQF笔记M1L3泰勒级数和转移概率密度函数

CQF笔记M1L3泰勒级数和转移密度函数Module 1 Building Blocks of Quant FinanceLecture 2 Taylor Series and Transition Density Functions泰勒级数期权价格的泰勒级数trinomial random walk和转移密度函数Similarity solutions 求解过程 Module 1 Building Blocks of Quant F…
暂无图片
编程学习 ·

面向对象到底是什么

面向对象编程OOP,全称 Object Oriented Programming两个基础概念:类(class)和对象(object)一种编程范式或编程风格。它以类或对象作为组织代码的基本单元,并将封装、抽象、继承、多态四个特性,作为代码设计和实现的基石面向对象编程语言OOPL,全称 Object Oriented Pro…
暂无图片
编程学习 ·

vc++ GDI+实现以鼠标为中心缩放图片(并且可以拖动)

按以下步骤操作,即可实现。1. 首先创建一个基于对话框的MFC程序,然后把下面两个文件分别保存为.h文件和 .cpp文件//InitGdiplus.h #pragma once#include <GdiPlus.h> using namespace Gdiplus;class CInitGdiplus { public:CInitGdiplus(void);~CInitGdiplus(void);pri…
暂无图片
编程学习 ·

LeetCode第47题 全排列 II

题目描述 给定一个可包含重复数字的序列,返回所有不重复的全排列。解题思路 1、题意理解,该序列有重复的数字,需要用一个boolean变量来标记该数字是否已经加入列表中 2、如果无法想象需要在哪里剪枝,画图。这里以[1,1,2]的全排列为例。圈蓝圈的表示需要剪枝的地方。代码:i…
暂无图片
编程学习 ·

POJ1270 Following Orders(拓扑排序+dfs回溯)

POJ1270 Following Orders(拓扑排序+dfs回溯) Description Order is an important concept in mathematics and in computer science. For example, Zorn’s Lemma states: ``a partially ordered set in which every chain has an upper bound contains a maximal element.’…
暂无图片
编程学习 ·

QT布局与信息和槽

实训第一天知识记录QT编码出现问题解决写代码出问题怎么办计算器编码的问题以及记录三种写法Hello World及注意事项布局的代码实现下一篇 信号,槽,以及connect()方法 QT编码出现问题解决 方法一: 找到工具栏——选项——kits 方法二: 项目中的构建目录 方法三: 右击清楚…
暂无图片
编程学习 ·

ROS成长-wiki-ros教程整理 一

初学者学习ROS的一个很好的途径就是通过wiki教程来初步了解ros、安装ros、操作简单功能。了解后需要进阶学习可以参考各种开源项目,请教技术大牛博客大神等(可以参考古月居博客) 。 wiki是初学者跳不开的学习过程。学习过程中,哪管它前路坎坷,进一步就有一步的成长。http:…
暂无图片
编程学习 ·

2.2.1String字符串

字符串比较equals():s1.equals(s2); equalsIgnoreCase():忽略大小写比较。去首尾空白字符 trim():" \tHello\r\n ".trim(); // "Hello" 替换子串根据字符或字符串替换:String s = "hello"; s.replace(l, w); // "hewwo",所有字符l…
暂无图片
编程学习 ·

目标检测算法R-CNN系列之Faster R-CNN

Faster R-CNN是在Fast R-CNN的基础上做了进一步的改进,主要解决的问题就是候选框的生成,通过使用anchor box机制,大大的提高了检测的速度以及效果。有关R-CNN以及Fast R-CNN可以点击链接,进行了解。下面将详细的介绍Faster R-CNN目标检测算法。1、网络架构 从上图中…
暂无图片
编程学习 ·

Java-WrapperClass及其转化

java里的变量分为primitive type和reference type两种。primitive type是int, char, double啥的,reference type(Wrapper Class)就是Integer, String这些。 我一直对reference type互相转化有点记不住,看了几个视频学习了一下。发现是因为对reference type(Wrapper Class)原理…