আমাদের দুটি স্ট্রিং দেওয়া হয়েছে, ধরা যাক str1 এবং str2 অক্ষর সম্বলিত এবং কাজটি হল উভয় স্ট্রিং-এর সাধারণ অনুবর্তনগুলি গণনা করা। নিচের প্রোগ্রামে আমরা ডাইনামিক প্রোগ্রামিং ব্যবহার করছি এবং এর জন্য আমাদের জানতে হবে ডাইনামিক প্রোগ্রামিং কি এবং কোন সমস্যায় এটি ব্যবহার করা যেতে পারে।
ডায়নামিক প্রোগ্রামিং পদ্ধতি সমস্যাটিকে ছোট এবং এখনও ছোট সম্ভাব্য উপ-সমস্যাগুলিতে ভাগ করে ভাগ করে জয় করার মতো। কিন্তু ভিন্নভাবে, ভাগ করুন এবং জয় করুন, এই উপসমস্যাগুলি স্বাধীনভাবে সমাধান করা হয় না। বরং, এই ছোট সাব-সমস্যাগুলির ফলাফলগুলি মনে রাখা হয় এবং অনুরূপ বা ওভারল্যাপ করা উপ-সমস্যাগুলির জন্য ব্যবহার করা হয়৷
ডায়নামিক প্রোগ্রামিং ব্যবহার করা হয় যেখানে আমাদের সমস্যা হয়, যেগুলিকে একই রকম সাব-প্রবলেমগুলিতে ভাগ করা যায়, যাতে তাদের ফলাফলগুলি পুনরায় ব্যবহার করা যায়। বেশিরভাগ ক্ষেত্রে, এই অ্যালগরিদমগুলি অপ্টিমাইজেশনের জন্য ব্যবহার করা হয়। ইন-হ্যান্ড সাব-সমস্যা সমাধান করার আগে, গতিশীল অ্যালগরিদমগুলি পূর্বে সমাধান করা উপ-সমস্যাগুলির ফলাফলগুলি পরীক্ষা করার চেষ্টা করবে। সর্বোত্তম সমাধান অর্জনের জন্য উপ-সমস্যাগুলির সমাধানগুলিকে একত্রিত করা হয়৷
৷তাই আমরা বলতে পারি −
Input − string str1 = “abc” String str2 = “ab” Output − count is 3
ব্যাখ্যা − প্রদত্ত স্ট্রিংগুলি থেকে সাধারণ অনুগামীগুলি গঠিত হয়:{'a', 'b', 'ab'}।
Input − string str1 = “ajblqcpdz” String str2 = “aefcnbtdi” Output − count is 11
সাধারণ অনুসৃতিগুলি হল৷ − প্রদত্ত স্ট্রিংগুলি থেকে সাধারণ অনুগামীগুলি গঠিত হয়:{ “a”, “b”, “c”, “d”, “ab”, “bd”, “ad”, “ac”, “cd”, “abd” , “acd” }
নিম্নলিখিত প্রোগ্রামে ব্যবহৃত পদ্ধতি
-
দুটি স্ট্রিং ইনপুট করুন আসুন str1 এবং str2 বলি।
-
length() ফাংশন ব্যবহার করে প্রদত্ত স্ট্রিংটির দৈর্ঘ্য গণনা করুন যা একটি স্ট্রিং-এর অক্ষরের সংখ্যা অনুযায়ী একটি পূর্ণসংখ্যা মান প্রদান করবে এবং str1-এর জন্য len1 এবং str2-এর জন্য len2-এ সংরক্ষণ করবে।
-
ডায়নামিক প্রোগ্রামিং বাস্তবায়নের জন্য একটি 2-ডি অ্যারে তৈরি করুন আসুন বলি arr[len1+1][len2+1]
-
i to 0 এর জন্য লুপ শুরু করুন যতক্ষণ না i len1 থেকে কম হয়
-
লুপের ভিতরে, j থেকে 0 এর জন্য আরেকটি লুপ শুরু করুন যতক্ষণ না j len2 থেকে কম হয়
-
লুপের ভিতরে, IF str1[i-1] =str2[j-1] চেক করুন তারপর arr[i][j] =1 + arr[i][j-1] + arr[i-1][j]<সেট করুন /P>
-
অন্যথায়, তারপর arr[i][j] =arr[i][j-1] + arr[i-1][j] =arr[i-1][j-1]
সেট করুন -
রিটার্ন arr[len1][len2]
-
ফলাফল প্রিন্ট করুন।
উদাহরণ
#include <iostream>
using namespace std;
// To count the number of subsequences in the string
int countsequences(string str, string str2){
int n1 = str.length();
int n2 = str2.length();
int dp[n1+1][n2+1];
for (int i = 0; i <= n1; i++){
for (int j = 0; j <= n2; j++){
dp[i][j] = 0;
}
}
// for each character of str
for (int i = 1; i <= n1; i++){
// for each character in str2
for (int j = 1; j <= n2; j++){
// if character are same in both
// the string
if (str[i - 1] == str2[j - 1]){
dp[i][j] = 1 + dp[i][j - 1] + dp[i - 1][j];
}
else{
dp[i][j] = dp[i][j - 1] + dp[i - 1][j] - dp[i - 1][j - 1];
}
}
}
return dp[n1][n2];
}
int main(){
string str = "abcdejkil";
string str2 = "bcdfkaoenlp";
cout <<"count is: "<<countsequences(str, str2) << endl;
return 0;
} উদাহরণ
আমরা উপরের কোডটি চালালে আমরা নিম্নলিখিত আউটপুট পাব −
count is: 51
