মান লেযিয়ে A এবং B অ্যারের পূর্ণসংখ্যাগুলো ক্রমশ দুটি আলাদা অনুভূমিক রেখায় লেখা হয়েছে। এখন আমরা সংযোগ রেখা আঁকতে পারি: একটি সরল রেখা A[i] এবং B[j]-কে সংযুক্ত করবে যদি -
A[i] == B[j];
আঁকা রেখা অন্য কোনো সংযোগ রেখা (অনুভূমিক ব্যতীত) ছেদ করে না।
ধরে রাখতে হবে যে সংযোগ রেখাগুলো এন্ডপয়েন্টে যেকোনোভাবে ছেদ করতে পারবে না - প্রতিটি সংখ্যা শুধু একটি সংযোগ রেখার অংশ হতে পারে। সর্বাধিক সংখ্যক সংযোগ রেখা খুঁজে বের করতে হবে। ইনপুট [1,4,2] এবং [1,2,4] হলে আউটপুট হবে ২।
| 1 | 4 | 2 |
| 1 | 2 | 4 |
ডায়াগ্রাম অনুযায়ী ২টি আনক্রসড লাইন আঁকা যায়। ৩টি আঁকা যাবে না, কারণ A[1]=4 থেকে B[2]=4 পর্যন্ত의 রেখা A[2]=2 থেকে B[1]=2 পর্যন্তের রেখাকে ছেদ করবে।
এটি সমাধান করার জন্য আমরা নিচের ধাপগুলো অনুসরণ করব -
solve() নামে একটি মেথড সংজ্ঞায়িত করুন, যা i, j, অ্যারে A, অ্যারে B এবং dp ম্যাট্রিক্স নেবে
যদি i অ্যারে A-এর রেঞ্জ বাইরে হয়, ০ রিটার্ন করুন
যদি j অ্যারে B-এর রেঞ্জ বাইরে হয়, ০ রিটার্ন করুন
nj := j
যখন nj < B.size() এবং B[nj] != A[i], nj বড়ান
temp := 1 যদি nj < B.size() হয়, অন্যথায় ০
ret := max(solve(i+1, j, A, B, dp), temp + solve(i+1, nj+1, A, B, dp))
dp[i][j] := ret এবং ret রিটার্ন করুন
মেইন মেথড থেকে - n := A.size(), m := B.size()
n x m আকারের dp ম্যাট্রিক্স তৈরি করুন, -1 দিয়ে পূরণ করুন
solve(0, 0, A, B, 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
