Computer >> Máy Tính >  >> Lập trình >> C ++

Dòng Uncrossed trong C ++

Giả sử chúng ta đã viết các số nguyên của A và B (theo thứ tự đã cho) trên hai đường ngang riêng biệt. Bây giờ, chúng ta có thể vẽ các đường nối:một đường thẳng nối hai số A [i] và B [j] sao cho -

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

  • Đường chúng tôi vẽ không giao với bất kỳ đường kết nối nào khác (không nằm ngang).

Chúng ta phải ghi nhớ rằng các đường kết nối không thể cắt nhau ngay cả ở các điểm cuối - mỗi số chỉ có thể thuộc về một đường kết nối. Tìm số đoạn thẳng nối tối đa. Vì vậy, nếu đầu vào là [1,4,2] và [1,2,4], thì đầu ra sẽ là 2.

1 4 2
1 2 4

Chúng ta có thể vẽ 2 đường thẳng không chéo nhau như trong sơ đồ. Chúng ta không thể vẽ 3 đường thẳng chéo nhau, điều này là do đường thẳng từ A [1] =4 đến B [2] =4 sẽ cắt đường từ A [2] =2 đến B [1] =2.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

  • Xác định một phương thức có tên là giải quyết (), phương thức này sẽ lấy, i, j, mảng A, mảng B và ma trận dp

  • nếu tôi nằm ngoài phạm vi của mảng A, hãy trả về 0

  • nếu j nằm ngoài phạm vi của mảng B, thì trả về 0

  • nj:=j

  • trong khi nj

    • tăng nj lên 1

  • temp:=1 khi nj

  • ret:=max of (giải quyết (i + 1, j, A, B, dp) và tạm thời) + giải quyết (i + 1, nj + 1, A, B, dp)

  • dp [i, j]:=ret và trả về ret

  • Từ phương thức chính

  • n:=kích thước của A, m:=kích thước của B

  • tạo ma trận dp có kích thước n x m và điền vào - 1

  • gọi giải quyết (0, 0, A,, dp)

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ 

#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));
}

Đầu vào 

[1,4,2]
[1,2,4]

Đầu ra 

2