C ++中的非交叉线

假设我们在两条分开的水平线上写了A和B的整数(按给定的顺序)。现在,我们可以绘制连接线:连接两个数字A [i]和B [j]的直线,使得-

  • A [i] == B [j];

  • 我们绘制的线不与任何其他连接(非水平)线相交。

我们必须记住,即使在端点处,连接线也不能相交-每个数字只能属于一条连接线。查找最大连接线数。因此,如果输入类似于[1,4,2]和[1,2,4],则输出将为2。

142
124

我们可以在图中绘制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