আমাদের N এবং K দুটি ইন্টিজার দেওয়া আছে। N দৈর্ঘ্যের বাইনারি স্ট্রিং (০ এবং ১) তৈরি করতে হবে যাতে সেগুলোতে K বার সংলগ্ন ১ থাকে। যেমন N=3, K=2 হলে ১১১ স্ট্রিংয়ে সংলগ্ন ১ দুবার (K বার) পাওয়া যায়। ০১১ এবং ১১০-এ একবার পাওয়া যায়।
এটি ৩D ডাইনামিক প্রোগ্রামিং দিয়ে সমাধান করা হয়। count[x][y][z] এরে ব্যবহার করা হয় যেখানে x = N, y = K, z = স্ট্রিংয়ের শেষ ডিজিট (০ বা ১)।
- N=1 হলে স্ট্রিং "০" এবং "১", সংলগ্ন ১-এর কাউন্ট ০। সুতরাং count[1][K][0] = count[1][K][1] = 0।
- শেষ ডিজিট ০ হলে: count[N][K][0] = count[N-1][K][0] + count[N-1][K][1]
- শেষ ডিজিট ১ হলে: count[N][K][1] = count[N-1][K][0] + count[N-1][K-1][1]
- মোট স্ট্রিং = count[N][K][0] + count[N][K][1]
ইনপুট
N=4, K=2
আউটপুট
Count of strings: 2
ব্যাখ্যা: ১১১০, ০১১১ - এই দুটি স্ট্রিংয়ের দৈর্ঘ্য ৪ এবং সংলগ্ন ১ দুবার পাওয়া যায়।
ইনপুট
N=3, K=1
আউটপুট
Count of strings: 2
ব্যাখ্যা: ১১০, ০১১ - দৈর্ঘ্য ৩ এবং সংলগ্ন ১ একবার। ১১১-এ দুবার পাওয়া যায়।
প্রোগ্রামে ব্যবহৃত পদ্ধতি
- N এবং K ইন্টিজার হিসেবে স্টোর করা।
- stringcount(int n, int k) ফাংশন স্ট্রিং কাউন্ট রিটার্ন করে।
- count[i][j][0/1] এরে দিয়ে দৈর্ঘ্য i, j বার সংলগ্ন ১, এবং শেষ ডিজিট ০/১ olan স্ট্রিংর সংখ্যা স্টোর করা।
- বেইস কেস: count[1][0][0] = 1; count[1][0][1] = 1;
- i=2 থেকে n পর্যন্ত এবং j=0 থেকে k পর্যন্ত লুপে DP টেবিল আপডেট করা।
- শেষে count[n][k][0] + count[n][k][1] রিটার্ন করা।
উদাহরণ কোড
#include <bits/stdc++.h>
using namespace std;
int stringcount(int n, int k){
int count[n + 1][k + 1][2] = {0};
count[1][0][0] = 1;
count[1][0][1] = 1;
for (int i = 2; i <= n; i++) {
for (int j = 0; j <= k; j++) {
count[i][j][0] = count[i - 1][j][0] + count[i - 1][j][1];
count[i][j][1] = count[i - 1][j][0];
if (j - 1 >= 0)
count[i][j][1] += count[i - 1][j - 1][1];
}
}
int result = count[n][k][0] + count[n][k][1];
return result;
}
int main(){
int N = 6, K = 3;
cout << "Strings of length 6 and 3 adjacent 1's in each :" << stringcount(N, K);
return 0;
}আউটপুট
Strings of length 6 and 3 adjacent 1's in each :7
