मान लीजिए, आप एक पेशेवर चोर हैं। और आप एक सड़क के किनारे घरों को लूटने की योजना बना रहे हैं। प्रत्येक घर में एक निश्चित मात्रा में पैसा जमा है। सभी घर एक वृत्त में व्यवस्थित हैं। इसका मतलब है कि पहला घर आखिरी घर का पड़ोसी है। हमें ध्यान रखना होगा कि आसन्न घरों में सुरक्षा प्रणाली जुड़ी हुई है और यह स्वचालित रूप से पुलिस से संपर्क करेगी यदि एक ही रात में दो आसन्न घरों में सेंध लगाई गई थी। तो यदि हमारे पास प्रत्येक घर के पैसे की मात्रा को दर्शाने वाले इंटीजर्स की एक सूची है, तो पुलिस को सतर्क किए बिना एक रात में आप जितना अधिकतम पैसा लूट सकते हैं उसे निर्धारित करें। तो यदि ऐरे [1,2,3,1] है, तो आउटपुट 4 होगा।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे −
- हम solve() नामक एक मॉड्यूल का उपयोग कर रहे हैं, जो ऐरे, स्टार्ट और एंड लेगा, जो नीचे की तरह कार्य करेगा −
- ans := nums[start]
- डायनामिक प्रोग्रामिंग के लिए एक टेबल बनाएं, जिसका नाम dp है, और आकार nums के आकार के समान है।
- dp[start] := nums[start]
- i := start + 1 से end तक
- last := dp[i – 1]
- lastToLast := 0 जब i – 2, अन्यथा dp[i – 2]
- dp[i] := nums[i] + lastToLast और last का अधिकतम
- ans := dp[i] और ans का अधिकतम
- ans लौटाएं
- लूट इस तरह की जाती है −
- n := nums का आकार
- यदि n शून्य है, तो 0 लौटाएं
- यदि n = 1, तो nums[0] लौटाएं
- solve(nums, 0, n - 2), solve(nums, 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
