C++의 교차되지 않은 줄

<시간/>

두 개의 개별 수평선에 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
가 필요합니다.
i가 배열 A의 범위를 벗어나면 0을 반환합니다.
j가 배열 B의 범위를 벗어나면 0을 반환합니다.
nj :=j
동안 nj
- nj를 1 증가
temp :=nj
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의 크기
크기가 n x m인 행렬 dp를 만들고 – 1
로 채웁니다.
해결(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]