【C++动态规划 最长公共子序列】1035. 不相交的线|1805

本文涉及知识点

C++动态规划

LeetCode1035. 不相交的线

在两条独立的水平线上按给定的顺序写下 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, nums2.length <= 500
1 <= nums1[i], nums2[j] <= 2000

# 动态规划的状态

性质一：令连线(i,j)在nums1的下标是i，nums2的下标是j。则两条连线(i1,j1)，(i2,j2)，其中i1 < i2，则j1 < j2，否则会交叉。
性质二：我们将各线按i的升序排序排序，根据性质一，则j也是升序。
性质三：令某最优解是{KaTeX parse error: Undefined control sequence: \cdost at position 1: \̲c̲d̲o̲s̲t̲(i1,j1)、(i2,j2)、（i3,j3）KaTeX parse error: Undefined control sequence: \cdost at position 1: \̲c̲d̲o̲s̲t̲}。如果存在j1<j4<j2,则将j2换成j4也是最优解。

动态规划的状态表示

dp[i][j]表示，所有线的上端点下标 <= i，下端下标<=j，且最后一条连线的下端点下标是j。dp[i][j] = -n-1表示不存在的可能。下标从1开始。空间复杂度：O(nm)

动态规矩的转移方程+双指针

dp[i+1] = dp[i] 没有选择上端点i。
nums[j1] == nums[i] 且j1 > j 且j1最小，如果存在合法的j1，则j1 = m
MaxSelf(dp[i+1][j1+1] ， dp[i][j]+1）
时间复杂度：O(nm)

动态规划的填表顺序

枚举前置状态
for(i = 0 To n-1） j = 0 To m-1

动态规划的初始化

dp[0][0]=0，其它全为-n-1

动态规划的返回值

max(dp.back())

代码

核心代码

classSolution{public:intmaxUncrossedLines(vector<int>& nums1, vector<int>& nums2){constint N = nums1.size();constint M = nums2.size(); vector<vector<int>>dp(N +1, vector<int>(M +1,-N-1)); dp[0][0]=0;for(int i =0; i < N; i++){ dp[i +1]= dp[i];for(int j =0,j1=0; j < M; j++){while((j1 < M)&&((nums2[j1]!= nums1[i])||(j1 < j))){ j1++;}if(j1 >= M)continue; dp[i +1][j1 +1]=max(dp[i +1][j1 +1], dp[i][j]+1);}}return*max_element(dp.back().begin(), dp.back().end());}};

单元测试

vector<int> nums1, nums2;TEST_METHOD(TestMethod1){ nums1 ={1,4,2}, nums2 ={1,2,4};auto res =Solution().maxUncrossedLines(nums1, nums2);AssertEx(2, res);}TEST_METHOD(TestMethod12){ nums1 ={2,5,1,2,5}, nums2 ={10,5,2,1,5,2};auto res =Solution().maxUncrossedLines(nums1, nums2);AssertEx(3, res);}TEST_METHOD(TestMethod13){ nums1 ={1,3,7,1,7,5}, nums2 ={1,9,2,5,1};auto res =Solution().maxUncrossedLines(nums1, nums2);AssertEx(2, res);}

扩展阅读

视频课程

先学简单的课程，请移步ZEEKLOG学院，听白银讲师（也就是鄙人）的讲解。
https://edu.ZEEKLOG.net/course/detail/38771
如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.ZEEKLOG.net/lecturer/6176

测试环境

操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。