বিবেচনা করুন, আপনি একজন পেশাদার ডাকাত। এবং আপনি রাস্তার পাশে বাড়ি লুট করার পরিকল্পনা করছেন। প্রতিটি বাড়িতে নির্দিষ্ট পরিমাণ অর্থ জমা থাকে। সমস্ত ঘর একটি বৃত্তে সাজানো হয়। তার মানে প্রথম ঘর শেষ বাড়ির প্রতিবেশী। আমাদের মনে রাখতে হবে যে পাশের বাড়িতে নিরাপত্তা ব্যবস্থা সংযুক্ত আছে এবং একই রাতে দুটি পার্শ্ববর্তী বাড়িতে ভাঙা হলে এটি স্বয়ংক্রিয়ভাবে পুলিশের সাথে যোগাযোগ করবে। তাই যদি আমাদের কাছে প্রতিটি বাড়ির টাকার পরিমাণের প্রতিনিধিত্বকারী পূর্ণসংখ্যার একটি তালিকা থাকে, তাহলে পুলিশকে সতর্ক না করে আপনি এক রাতে সর্বোচ্চ কত টাকা লুট করতে পারবেন তা নির্ধারণ করুন। সুতরাং যদি অ্যারে [1,2,3,1] হয়, তাহলে আউটপুট হবে 4।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
- আমরা সমাধান() নামক একটি মডিউল ব্যবহার করছি, যেটি অ্যারে, শুরু এবং শেষ নেবে, যা নিচের মত কাজ করবে -
- উত্তর :=সংখ্যা[শুরু]
- ডাইনামিক প্রোগ্রামিংয়ের জন্য একটি টেবিল তৈরি করুন, সেটির নাম dp, এবং আকারটি সংখ্যা আকারের সমান।
- dp[start] :=nums[start]
- এর জন্য i :=শুরু + 1 শেষ করতে
- শেষ :=dp[i – 1]
- lastToLast :=0 যখন i – 2, অন্যথায় dp[i – 2]
- dp[i] :=সংখ্যার সর্বাধিক[i] + lastToLast এবং শেষ
- উত্তর :=সর্বোচ্চ dp[i] এবং ans
- উত্তর ফেরত দিন
- ছিনতাই করা হয় নিচের মত -
- n :=সংখ্যার আকার
- যদি n শূন্য হয়, তাহলে 0 ফেরত দিন
- যদি n =1 হয়, তাহলে সংখ্যা ফেরত দিন[0]
- সর্বোচ্চ রিটার্ন (সংখ্যা, 0, n - 2), সমাধান (সংখ্যা, 1, n - 1)
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
উদাহরণ
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int solve(vector <int>& nums, int start, int end){
int ans = nums[start];
vector <int> dp(nums.size());
dp[start] = nums[start];
for(int i = start + 1; i <= end; i++){
int last = dp[i - 1];
int lastToLast = i - 2 < start? 0 : dp[i - 2];
dp[i] = max(nums[i] + lastToLast, last);
ans = max(dp[i], ans);
}
return ans;
}
int rob(vector<int>& nums) {
int n = nums.size();
if(!n)return 0;
if(n == 1)return nums[0];
return max(solve(nums, 0, n - 2), solve(nums, 1, n - 1));
}
};
main(){
vector<int> v = {1,2,3,5};
Solution ob;
cout << ob.rob(v);
} ইনপুট
[1,2,3,5]
আউটপুট
7
