假设我们在两条分开的水平线上写了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