C++の交差していない行

AとBの整数を（指定された順序で）2本の別々の水平線に書き込んだとします。ここで、接続線を描くことができます。つまり、-

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

• 他の接続（非水平）線と交差しない、描画する線。

接続線は端点でも交差できないことに注意する必要があります。各番号は1つの接続線にのみ属することができます。接続線の最大数を見つけます。したがって、入力が[1,4,2]や[1,2,4]の場合、出力は2になります。

図のように2本の交差していない線を描くことができます。これは、A [1]=4からB[2]=4までの線がA[2]=2からB[1]=2までの線と交差するためです。

これを解決するには、次の手順に従います-

• Solve（）というメソッドを定義します。これには、i、j、配列A、配列B、および行列dp

  が必要です。

• iが配列Aの範囲外の場合は、0を返します

• jが配列Bの範囲外の場合は、0を返します

• nj：=j

• njではありません

  • njを1増やします

• temp：=1（nj ）

• ret：=max of（solve（i + 1、j、A、B、dp）and temp）+ resolve（i + 1、nj + 1、A、B、dp）

• dp [i、j]：=retおよびreturnret

• メインメソッドから

• 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