मान लीजिए कि हमने A और B के पूर्णांकों को दो अलग-अलग क्षैतिज रेखाओं पर (उनके दिए गए क्रम में) लिखा है। अब, हम जोड़ने वाली रेखाएँ खींच सकते हैं:दो संख्याओं A[i] और B[j] को जोड़ने वाली एक सीधी रेखा इस प्रकार कि -
-
ए [i] ==बी [जे];
-
वह रेखा जो हम खींचते हैं जो किसी अन्य जोड़ने वाली (गैर-क्षैतिज) रेखा को नहीं काटती है।
हमें यह ध्यान रखना होगा कि जोड़ने वाली रेखाएं अंतिम बिंदुओं पर भी प्रतिच्छेद नहीं कर सकती हैं - प्रत्येक संख्या केवल एक जोड़ने वाली रेखा से संबंधित हो सकती है। कनेक्टिंग लाइनों की अधिकतम संख्या पाएं। तो अगर इनपुट [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 तक की रेखा को काटेगी।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
-
हल () नामक एक विधि को परिभाषित करें, इसमें i, j, सरणी A, सरणी B और मैट्रिक्स dp लगेगा।
-
अगर मैं सरणी ए की सीमा से बाहर हूं, तो 0 पर लौटें
-
यदि j सरणी B की सीमा से बाहर है, तो 0 पर लौटें
-
एनजे:=जे
-
जबकि nj
-
nj को 1 से बढ़ाएं
-
-
अस्थायी:=1 जब nj
-
रिट:=अधिकतम (समाधान (i + 1, j, A, B, dp) और अस्थायी) + हल करें (i + 1, nj + 1, A, B, dp)
-
dp[i, j] :=ret and return ret
-
मुख्य विधि से
-
n:=A का आकार, m:=B का आकार
-
n x m आकार का एक मैट्रिक्स dp बनाएं और इसे - 1
. से भरें -
कॉल हल (0, 0, ए, डीपी)
आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -
उदाहरण
#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