六大算法之动态规划_动态规划100题

六大算法之动态规划_动态规划100题在两条独立的水平线上按给定的顺序写下 nums1 和 nums2 中的整数。现在,可以绘制一些连接两个数字 nums1[i] 和 nums2[j] 的直线,这些直线需要同时满足满足:nums1[i] == nums2[j]且绘制的直线不与任何其他连线(非水平线)相交。请注意,连线即使在端点也不能相交:每个数字只能属于一条连线。以这种方法绘制线条,并返回可以绘制的最大连线数。示例 1:输入:nums1 = [1,4,2], nums2 = [1,2,4]输出:2解释:可以画出两条不交叉的

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

在两条独立的水平线上按给定的顺序写下 nums1 和 nums2 中的整数。

现在,可以绘制一些连接两个数字 nums1[i] 和 nums2[j] 的直线,这些直线需要同时满足满足:

nums1[i] == nums2[j]
且绘制的直线不与任何其他连线(非水平线)相交。
请注意,连线即使在端点也不能相交:每个数字只能属于一条连线。

以这种方法绘制线条,并返回可以绘制的最大连线数。

示例 1:


输入:nums1 = [1,4,2], nums2 = [1,2,4]
输出:2
解释:可以画出两条不交叉的线,如上图所示。 
但无法画出第三条不相交的直线,因为从 nums1[1]=4 到 nums2[2]=4 的直线将与从 nums1[2]=2 到 nums2[1]=2 的直线相交。
示例 2:

输入:nums1 = [2,5,1,2,5], nums2 = [10,5,2,1,5,2]
输出:3
示例 3:

输入:nums1 = [1,3,7,1,7,5], nums2 = [1,9,2,5,1]
输出:2
 

提示:

1 <= nums1.length <= 500
1 <= nums2.length <= 500
1 <= nums1[i], nums2[i] <= 2000

动态规划

const int N = 2010;
const int M = 510;
int Hash[N];
int f[M][M] = { 
   0};
class Solution { 
   
public:
    int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2) { 
   
        int n = nums1.size(),m = nums2.size();
        memset(Hash,0,sizeof Hash);
        for(int j = 1;j <= m;j ++){ 
   
            Hash[nums2[j - 1]] = j;
            for(int i = 1;i <= n;i ++){ 
   
                f[i][j] = f[i - 1][j];
                if(Hash[nums1[i - 1]] != 0){ 
   
                    f[i][j] = max(f[i][j],f[i - 1][Hash[nums1[i - 1]] - 1] + 1);
                }
            }
        }
        return f[n][m];
    }
};
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/169069.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • PHP的HTTP客户端:Guzzle的简单使用

    PHP的HTTP客户端:Guzzle的简单使用

  • cut it out什么意思_cutout例句

    cut it out什么意思_cutout例句1.几种数据增强的比较Mixup:将随机的两张样本按比例混合,分类的结果按比例分配;Cutout:随机的将样本中的部分区域cut掉,并且填充0像素值,分类的结果不变;CutMix:就是将一部分区域cut掉但不填充0像素而是随机填充训练集中的其他数据的区域像素值,分类结果按一定的比例分配区别上述三种数据增强的区别:cutout和cutmix就是填充区域像素值的区别;mixup和cutmix是混合两种…

  • WPF实现界面动态布局

    WPF实现界面动态布局

  • AngularJS自己定义标签加入回调函数eval()

    AngularJS自己定义标签加入回调函数eval()

  • mysql 查看函数fsync_sync/fsync/fdatasync的简单比较

    mysql 查看函数fsync_sync/fsync/fdatasync的简单比较此文主要转载自官网上有关于MySQL的flushmethod的设置参数说明,但可能很多人不太明白。下文就详细说明此问题。首先官网的说明如下:http://dev.mysql.com/doc/refman/5.6/en/innodb-parameters.html#sysvar_innodb_flush_methodinnodb_flush_methodCommand-LineFormat–i…

  • JavaScript基础大总结

    JavaScript基础大总结✍初始JavaScirptJavaScript是世界上最流行的语言之一,是一种运行在客户端的脚本语言(Script是脚本的意思)脚本语言:不需要编译,运行过程中由js解释器(js引擎)逐行来进行解释并执行现在也可以基于Node.js技术进行服务器端编程????浏览器执行JS简介浏览器分成两部分:渲染引擎和JS引擎渲染引擎:用来解析HTML与CSS,俗称内核,比如chrome浏览器的blink,老版本的webkitJS引擎:也称为JS解释器。用来读

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号