এই সমস্যায়, আমাদের n সংখ্যক বাড়ি দেওয়া আছে যাতে কিছু মান থাকে। আমাদের কাজ হলো বাড়ি থেকে চুরি করা সম্ভাব্য সর্বোচ্চ মান খুঁজে বের করা।
সমস্যা বিবরণ
আমাদের houses[] অ্যারে আছে যাতে প্রতিটি বাড়ির মান থাকে। একজন চোর বাড়ি চুরি করে কিন্তু সে দুটি आसন্ন বাড়ি থেকে চুরি করতে পারবেন না কারণ প্রতিবেশীরা জানতে পারেন। আমাদের চোর পiatric না করেই বাড়ি থেকে চুরি করা সম্ভাব্য সর্বোচ্চ মান বের করতে হবে।
উদাহরণ
ইনপুট
houses[] = {5, 2, 1, 6, 7, 9, 4, 3}
আউটপুট
23
ব্যাখ্যা
চুরি করা যাবে সর্বোচ্চ মান: 5, 6, 9, 3।
সমাধানের পদ্ধতি
সমস্যাটি ডাইনামিক প্রোগ্রামিং দিয়ে সমাধান করা যায়। যেহেতু চোর যদি i ইনডেক্সের বাড়ি থেকে চুরি করে, তবে (i+1) ইনডেক্সের বাড়ি থেকে চুরি করতে পারবে না।また (i-1) ইনডেক্সের বাড়ি থেকেও চুরি করা যাবে না।
সমাধানের জন্য আমরা n আকারের DP অ্যারে তৈরি করব। বেস কেস হিসেবে DP[0] = houses[0] এবং DP[1] = max(houses[0], houses[1])। তারপর ২ থেকে n-1 পর্যন্ত DP[i] = max(DP[i-2] + houses[i], DP[i-1])। DP অ্যারের শেষ মানই চুরি করা সম্ভাব্য সর্বোচ্চ মান।
C++ প্রোগ্রাম উদাহরণ (DP অ্যারে ব্যবহার করে)
#include <iostream>
using namespace std;
int calMax(int a, int b){
if(a > b)
return a;
return b;
}
int findMaxValuesStolen(int houses[], int n) {
if (n == 0)
return 0;
int DP[n];
DP[0] = houses[0];
DP[1] = calMax(houses[0], houses[1]);
for (int i = 2; i < n; i++)
DP[i] = calMax((houses[i] + DP[i-2]), DP[i-1]);
return DP[n-1];
}
int main() {
int houses[] = {5, 2, 1, 6, 7, 9, 4, 3};
int n = sizeof(houses)/sizeof(houses[0]);
cout << "The maximum possible values stolen from the houses is " << findMaxValuesStolen(houses, n);
return 0;
}
আউটপুট
The maximum possible values stolen from the houses is 23
স্পেস অপ্টিমাইজড পদ্ধতি (শুধু দুটি ভেরিয়েবল ব্যবহার করে)
DP-তে শুধু দুটি পূর্ববর্তী মান ব্যবহার হয়, তাই আমরা শুধু দুটি ভেরিয়েবল দিয়ে স্পেস কমপ্লেক্সিটি O(1) করতে পারি।
C++ প্রোগ্রাম উদাহরণ (অপ্টিমাইজড)
#include <iostream>
using namespace std;
int calMax(int a, int b){
if(a > b)
return a;
return b;
}
int findMaxValuesStolen(int houses[], int n) {
if (n == 0)
return 0;
int maxValStolen;
int val1 = houses[0];
int val2 = calMax(houses[0], houses[1]);
for (int i = 2; i < n; i++) {
maxValStolen = calMax((houses[i] + val1), val2);
val1 = val2;
val2 = maxValStolen;
}
return maxValStolen;
}
int main() {
int houses[] = {5, 2, 1, 6, 7, 9, 4, 3};
int n = sizeof(houses)/sizeof(houses[0]);
cout << "The maximum possible values stolen from the houses is " << findMaxValuesStolen(houses, n);
return 0;
}
আউটপুট
The maximum possible values stolen from the houses is 23
