At Coder Educational DP-F | DP Series(Episode-8)
Problem Description here
Problem: এই প্রব্লেমে আমাদেরকে দুটি স্ট্রিং দেয়া থাকবে। আমাদেরকে স্ট্রিং দুটির Longest Common Subsequence প্রিন্ট করতে হবে। যদি LCS এর লেন্থ বের করতে বলতো তাহলে শুধু ডিপি করা পর্যন্তই সীমাবদ্ধ থাকতো। কিন্তু, এখানে ডিপি সল্যুশন প্রিন্ট করতে হবে।
Recursive Solution:
১) এই প্রব্লেমের জন্য আমাদের দুটি স্টেট রাখতে হবে। একটি হচ্ছে আমি বর্তমানে প্রথম স্ট্রিং এর কোন পজিশনে আছি এবং অন্যটি হচ্ছে আমি এখন দ্বিতীয় স্ট্রিং এর কোন পজিশনে আছি।
২) যদি s1[pos1] == s2[pos2] হয় তবে এই ম্যাচটি কাউন্ট করে দুটি স্টেট এর ভ্যালু ১ বাড়িয়ে পরবর্তী ট্রাঞ্জিশনে যাওয়া ই বেটার।
৩) অন্যথায়, একবার pos1 কে বাড়িয়ে দেখবো এবং আবার pos2 কে বাড়িয়ে দেখবো। এবং LCS ম্যাক্সিমাইজ করবো।
এবার সল্যুশন প্রিন্ট কিভাবে করবো?
যেকোন রিকার্সিভ ডিপি প্রব্লেমের সল্যুশন প্রিন্ট এর ধাপগুলোঃ
১) হুবহু ডিপি ফাংশনটি কপি করে আরেকটি ফাংশন বানাবো যার রিটার্ণ টাইপ হবে void.
২) বেসকেসে শুধু return লিখবো।
৩) dp[state-1][state-2]...[state-k] != -1 হলে ক্যালকুলেটেড ভ্যালুটি রিটার্ণ করো এই লাইনদুটি বাদ দিবো।
৪) এখন, যেহেতু আমার ডিপি ফাংশন প্রতিটি ট্রাঞ্জিশনের ভ্যালুই পূর্বে ক্যালকুলেট করে রাখছে সেহেতু প্রব্লেম এর শর্ত অনুযায়ী আমার বর্তমান অবস্থা থেকে কোন অবস্থায় যাওয়া উচিৎ সেটি আমি বলতে পারবো। এবং যেদিকে যাওয়া উচিৎ সেদিকেই যাবো এবং Relevant Value টি প্রিন্ট করবো।
আশা করি কোড দেখলে বুঝতে পারবে।
| #include<bits/stdc++.h> | |
| using namespace std; | |
| int len1,len2,dp[3005][3005]; | |
| string s1,s2; | |
| int LCS(int pos1,int pos2) | |
| { | |
| if(pos1>=len1 || pos2>=len2) | |
| return 0; | |
| if(dp[pos1][pos2] != -1) | |
| return dp[pos1][pos2]; | |
| if(s1[pos1] == s2[pos2]) | |
| return dp[pos1][pos2] = 1+LCS(pos1+1,pos2+1); | |
| else | |
| return dp[pos1][pos2] = max(LCS(pos1+1,pos2),LCS(pos1,pos2+1)); | |
| } | |
| void Print(int pos1,int pos2) | |
| { | |
| if(pos1>=len1 || pos2>=len2){ | |
| printf("\n"); | |
| return; | |
| } | |
| if(s1[pos1] == s2[pos2]) | |
| { | |
| printf("%c",s1[pos1]); | |
| Print(pos1+1,pos2+1); | |
| } | |
| else | |
| { | |
| if(dp[pos1+1][pos2] >= dp[pos1][pos2+1]) | |
| Print(pos1+1,pos2); | |
| else | |
| Print(pos1,pos2+1); | |
| } | |
| } | |
| int main() | |
| { | |
| int i,j,k,ans; | |
| memset(dp , -1 , sizeof(dp)); | |
| cin>>s1>>s2; | |
| len1=s1.size(); | |
| len2=s2.size(); | |
| ans=LCS(0,0); | |
| Print(0,0); | |
| return 0; | |
| } |
Iterative Solution:
১) ইটারেটিভ ডিপি তে আমাদের dp[pos1][pos2] এর ভ্যালু ক্যালকুলেট করতে dp[pos1+1][pos2+1], dp[pos1+1][pos2], dp[pos1][pos2+1] এর ভ্যালু প্রয়োজন হয়। যেকারণে, pos1=sz1-1 , ... , 1 এবং pos2=sz2-1 , ... , 1 এই অর্ডারে ডিপি ভ্যালু ক্যালকুলেট করবো।
২) আর সল্যুশন প্রিন্ট অংশ আশা করি কোড দেখলেই বুঝবে।
| #include<bits/stdc++.h> | |
| using namespace std; | |
| int dp[3005][3005]; | |
| ///dp[i][j] means longest common subsequence of s1[i...sz1] & s2[j...sz2] | |
| int main() | |
| { | |
| int i,j,k,sz1,sz2,lcs; | |
| string s1,s2,ans=""; | |
| cin>>s1>>s2; | |
| sz1 = (int)s1.size(); | |
| sz2 = (int)s2.size(); | |
| ///Base Case | |
| for(j=0 ; j<=sz2 ; j++) | |
| dp[sz1][j] = 0; | |
| for(i=0 ; i<=sz1 ; i++) | |
| dp[i][sz2] = 0; | |
| for(int pos1=sz1-1 ; pos1 >= 0 ; pos1--){ | |
| for(int pos2=sz2-1 ; pos2 >= 0 ; pos2--){ | |
| if(s1[pos1] == s2[pos2]) | |
| dp[pos1][pos2] = 1 + dp[pos1+1][pos2+1]; | |
| else | |
| dp[pos1][pos2] = max(dp[pos1+1][pos2] , dp[pos1][pos2+1]); | |
| } | |
| } | |
| lcs = dp[0][0]; | |
| i = j = 0; | |
| while(i<sz1 && j<sz2){ | |
| if(s1[i] == s2[j]){ | |
| ans += s1[i]; | |
| i++; j++; | |
| } | |
| else{ | |
| if(dp[i+1][j] > dp[i][j+1]) | |
| i++; | |
| else | |
| j++; | |
| } | |
| } | |
| cout<<ans<<endl; | |
| return 0; | |
| } |
Happy Coding
Comments
Post a Comment