C ++中的非交叉线
假设我们在两条分开的水平线上写了A和B的整数（按给定的顺序）。现在，我们可以绘制连接线：连接两个数字A[i]和B[j]的直线，使得-
A[i]==B[j];
我们绘制的线不与任何其他连接（非水平）线相交。
我们必须记住，即使在端点处，连接线也不能相交-每个数字只能属于一条连接线。查找最大连接线数。因此，如果输入类似于[1,4,2]和[1,2,4]，则输出将为2。
我们可以在图中绘制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