सी++ में हाउस रॉबर II

विचार करें, आप एक पेशेवर लुटेरे हैं। और आप सड़क किनारे घरों को लूटने की योजना बना रहे हैं। प्रत्येक घर में एक निश्चित राशि जमा होती है। सभी घरों को एक सर्कल में व्यवस्थित किया गया है। इसका मतलब है कि पहला घर आखिरी घर का पड़ोसी है। हमें यह ध्यान रखना होगा कि बगल के घरों में सुरक्षा व्यवस्था जुड़ी हुई है और अगर एक ही रात में दो बगल के घरों को तोड़ा गया तो यह स्वचालित रूप से पुलिस से संपर्क करेगा। इसलिए यदि हमारे पास प्रत्येक घर की राशि का प्रतिनिधित्व करने वाले पूर्णांकों की एक सूची है, तो यह निर्धारित करें कि आप पुलिस को सतर्क किए बिना एक रात में अधिकतम कितनी धनराशि लूट सकते हैं। तो अगर ऐरे [1,2,3,1] है, तो आउटपुट 4 होगा।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

हम एक मॉड्यूल का उपयोग कर रहे हैं जिसे हल () कहा जाता है, जो सरणी लेगा, प्रारंभ और अंत करेगा, जो नीचे की तरह कार्य करेगा -
उत्तर:=अंक [शुरू]
डायनेमिक प्रोग्रामिंग के लिए एक टेबल बनाएं, जिसका नाम dp है, और आकार अंकों के आकार के समान है।
dp[शुरू] :=अंक [शुरू]
i के लिए:=प्रारंभ + 1 से अंत तक
- अंतिम:=डीपी[i - 1]
- lastToLast :=0 जब i – 2, अन्यथा dp[i – 2]
- dp[i] :=अधिकतम अंक[i] + lastToLast और last
- उत्तर:=अधिकतम डीपी[i] और उत्तर
वापसी उत्तर
लूटना नीचे की तरह किया जाता है -
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]