假设我们在两条分开的水平线上写了A和B的整数(按给定的顺序)。现在,我们可以绘制连接线:连接两个数字A [i]和B [j]的直线,使得-
A [i] == B [j];
我们绘制的线不与任何其他连接(非水平)线相交。
我们必须记住,即使在端点处,连接线也不能相交-每个数字只能属于一条连接线。查找最大连接线数。因此,如果输入类似于[1,4,2]和[1,2,4],则输出将为2。
1 | 4 | 2 |
1 | 2 | 4 |
我们可以在图中绘制2条不交叉的线。我们无法绘制3条不交叉的线,这是因为从A [1] = 4到B [2] = 4的线将与从A [2] = 2到B [1] = 2的线相交。
为了解决这个问题,我们将遵循以下步骤-
定义一个名为的方法solve()
,它将使用i,j,数组A,数组B和矩阵dp
如果我超出数组A的范围,则返回0
如果j超出数组B的范围,则返回0
nj:= j
而nj <B的大小,而B [nj]不是A [i]
使nj增加1
temp:= nj <B的大小时为1,否则为0
ret:=(solve(i + 1,j,A,B,dp)和temp)的最大值+ solve(i +1,nj + 1,A,B,dp)
dp [i,j]:= ret并返回ret
从主要方法
n:= A的大小,m:= B的大小
创建大小为nxm的矩阵dp,并用– 1填充
调用solve(0,0,A,,dp)
让我们看下面的实现以更好地理解-
#include <bits/stdc++.h> using namespace std; class Solution { public: int solve(int i, int j, vector <int>&A, vector <int>&B, vector < vector <int> >& dp){ if(i >= A.size()) return 0; if(j >= B.size()) return 0; if(dp[i][j] != -1) return dp[i][j]; int nj = j; while(nj < B.size() && B[nj] != A[i]) nj++; int ret = max(solve(i + 1, j, A, B, dp), (nj < B.size() ? 1 : 0) + solve(i + 1, nj + 1, A, B, dp)); return dp[i][j] = ret; } int maxUncrossedLines(vector<int>& A, vector<int>& B) { int n = A.size(); int m = B.size(); vector < vector <int > > dp(n, vector <int>(m, -1)); return solve(0, 0, A, B, dp); } }; main(){ vector<int> v1 = {1,4,2}; vector<int> v2 = {1,2,4}; Solution ob; cout << (ob.maxUncrossedLines(v1, v2)); }
[1,4,2] [1,2,4]
输出结果
2