এখানে আমরা একটি আকর্ষণীয় সমস্যা দেখতে পাব। ধরুন n এর একটি মান দেওয়া হল। আমাদের n দৈর্ঘ্যের সমস্ত স্ট্রিং খুঁজে বের করতে হবে, যাতে কোনো ধারাবাহিক 1s নেই। যদি n =2 হয়, তাহলে সংখ্যাগুলি হল {00, 01, 10}, সুতরাং আউটপুট হল 3৷
আমরা ডাইনামিক প্রোগ্রামিং ব্যবহার করে এটি সমাধান করতে পারি। ধরুন আমাদের একটি টেবিল আছে ‘a’ এবং ‘b’। যেখানে arr[i] দৈর্ঘ্য i এর বাইনারি স্ট্রিংগুলির সংখ্যা সংরক্ষণ করছে, যেখানে কোনো ধারাবাহিক 1s উপস্থিত নেই এবং 0 দিয়ে শেষ হচ্ছে। একইভাবে, b একই ধারণ করছে কিন্তু 1 দিয়ে শেষ হওয়া সংখ্যাগুলি। আমরা শেষ যেখানে 0 বা 1 যুক্ত করতে পারি 0, কিন্তু শেষটি 1 হলে শুধুমাত্র 0 যোগ করুন।
আসুন এই ধারণা পেতে অ্যালগরিদম দেখি।
অ্যালগরিদম
noConsecutiveOnes(n) -
Begin define array a and b of size n a[0] := 1 b[0] := 1 for i in range 1 to n, do a[i] := a[i-1] + b[i - 1] b[i] := a[i - 1] done return a[n-1] + b[n-1] End
উদাহরণ
#include <iostream>
using namespace std;
int noConsecutiveOnes(int n) {
int a[n], b[n];
a[0] = 1;
b[0] = 1;
for (int i = 1; i < n; i++) {
a[i] = a[i-1] + b[i-1];
b[i] = a[i-1];
}
return a[n-1] + b[n-1];
}
int main() {
cout << noConsecutiveOnes(4) << endl;
} আউটপুট
8
