హౌస్ రాబర్ లీట్‌కోడ్ సొల్యూషన్


కఠినత స్థాయి సులువు
తరచుగా అడుగుతుంది అమెజాన్ ఆపిల్ సిస్కో మైక్రోసాఫ్ట్ ఒరాకిల్
డైనమిక్ ప్రోగ్రామింగ్

సమస్యల నివేదిక

ఈ సమస్యలో ఒక వీధిలో ఇళ్ళు ఉన్నాయి మరియు హౌస్ దొంగ ఈ ఇళ్లను దోచుకోవాలి. కానీ సమస్య ఏమిటంటే, అతను ఒకటి కంటే ఎక్కువ ఇంటిని వరుసగా దోచుకోలేడు, అంటే ఒకదానికొకటి ప్రక్కనే. ప్రతి ఇంటి డబ్బు మొత్తాన్ని సూచించే ప్రతికూలత లేని పూర్ణాంకాల జాబితాను చూస్తే, అతను పొందగలిగే గరిష్ట మొత్తాన్ని మనం కనుగొనాలి.

ఉదాహరణ

nums = [1,2,3,1]
4

వివరణ:హౌస్ దొంగ

రాబ్ హౌస్ 1 (డబ్బు = 1) ఆపై దోపిడీ హౌస్ 3 (డబ్బు = 3).
మీరు దోచుకోగల మొత్తం మొత్తం = 1 + 3 = 4.

nums = [2,7,9,3,1]
12

వివరణ:

రాబ్ హౌస్ 1 (డబ్బు = 2), రాబ్ హౌస్ 3 (డబ్బు = 9), ఆపై 5 వ (డబ్బు = 1).
మీరు దోచుకోగల మొత్తం మొత్తం = 2 + 9 + 1 = 12.

అప్రోచ్

అత్యాశ విధానం ద్వారా ఈ సమస్యను పరిష్కరించలేరు.
ఒక ఉదాహరణ తీసుకుందాం:
nums = [1,7,9,5,1,3,4]

మేము శ్రేణిలో గరిష్ట మూలకం కోసం వెళితే (అనగా 9), మేము దాని ప్రక్కనే ఉన్న మొత్తాన్ని (అంటే 7 + 5) కోల్పోతాము. మరియు మనం కలిగి ఉన్న ఉత్తమమైనది మొత్తం 15 గా ఉంటుంది.

మేము సరి లేదా బేసి స్థాన మూలకాల కోసం వెళితే మనకు మొత్తం = 15 (7 + 5 + 3) మరియు బేసి మొత్తం = 15 (1 + 9 + 1 + 4) కూడా ఉన్నాయి.

ఈ ఉదాహరణకి వాంఛనీయ సమాధానం [7 + 5 + 4] = 12 అవుతుంది.

అందువల్ల ఈ రకమైన సమస్యను పరిష్కరించడానికి మేము అన్ని ఎంపికలను పునరావృతంగా శోధించాలి మరియు వాటి నుండి గరిష్టంగా ఎంచుకోవాలి. దీనిని సూచిద్దాం:

f (n) = మీరు మొదటి ఇంటి నుండి n వ ఇండెక్స్డ్ ఇంటికి దోచుకోగల అతిపెద్ద మొత్తం.
Ai = ith ఇండెక్స్ ఇంట్లో డబ్బు మొత్తం.

ప్రతి ఇంటి వద్ద దాన్ని దోచుకోవడం లేదా వదిలేయడం మాకు ఎంపిక.
కేసు 1 - మేము చివరి ఇంటిని ఎంచుకుంటే:
అప్పుడు, మేము (n-1) వ ఇంటిని ఎంచుకోలేము, అందుకే f (n) = An + f (n-2)
కేసు 2 - మేము చివరి ఇంటిని విడిచిపెడితే:
అప్పుడు, మేము (n-1) వ ఇల్లు వరకు గరిష్ట లాభంతో అంటుకుంటాము, అందుకే f (n) = f (n-1)

బేస్ కేసులను చూద్దాం.
n = 0, స్పష్టంగా f (0) = A0.
n = 1, తరువాత f (1) = గరిష్టంగా (A0, A1).

అందువల్ల మనం సూత్రాన్ని ఈ క్రింది విధంగా సంగ్రహించవచ్చు:
f (n) = గరిష్టంగా (An + f (n-2), f (n-1))

ఇది పునరావృత సూత్రం, ఇది సాధారణ పునరావృతం ద్వారా మేము అమలు చేయవచ్చు, అయితే ఇక్కడ సమయ సంక్లిష్టత O (2 ^ n) అవుతుంది. అందువల్ల మేము ఉపయోగిస్తాము డైనమిక్ ప్రోగ్రామింగ్ శ్రేణిలో ఇంటర్మీడియట్ ఫలితాలను చేరుకోండి మరియు నిల్వ చేయండి.
లెక్కించిన తరువాత మేము శ్రేణిలో n వ (చివరి) సూచిక వద్ద నిల్వ చేసిన విలువను తిరిగి ఇస్తాము.

అమలు

హౌస్ రాబర్ లీట్‌కోడ్ సొల్యూషన్ కోసం సి ++ ప్రోగ్రామ్

#include <bits/stdc++.h>
using namespace std;

int rob(vector<int>& nums)
{
    int n=nums.size();

    if(n==0) return 0;
    if(n==1) return nums[0];

    int a[n];

    a[0]=nums[0];
    a[1]=max(nums[0],nums[1]);

    for(int i=2;i<n;i++)
    a[i]=max(nums[i]+a[i-2], a[i-1]);

    return a[n-1];

}
int main() 
{
    vector<int> arr={1,2,3,1};
    
    cout<<rob(arr)<<endl;
    
  return 0; 
}
4

హౌస్ రాబర్ లీట్‌కోడ్ సొల్యూషన్ కోసం జావా ప్రోగ్రామ్

import java.util.*;
import java.lang.*;

class HouseRobber
{  
    public static int rob(int[] nums) {
        
        int n=nums.length;
        
        if(n==0) return 0;
        if(n==1) return nums[0];
        
        int a[]=new int[n];
       
        a[0]=nums[0];
        a[1]=Math.max(nums[0],nums[1]);
        
        for(int i=2;i<n;i++)
            a[i]=Math.max(nums[i]+a[i-2], a[i-1]);
        
        return a[n-1];
    }
    
    
    public static void main(String args[])
    {
        int arr[]={1,2,3,1};
        System.out.println(rob(arr));
    }
}
4

హౌస్ రాబర్ లీట్‌కోడ్ సొల్యూషన్ కోసం సంక్లిష్టత విశ్లేషణ

సమయం సంక్లిష్టత

పై) : మేము 1 వ ఇంటి నుండి n వ ఇంటికి ఒకే లూప్‌లో మళ్ళిస్తున్నాము, ఇక్కడ n అనేది మొత్తం గృహాల సంఖ్య.

అంతరిక్ష సంక్లిష్టత 

పై) : ఇంటర్మీడియట్ ఫలితాన్ని నిల్వ చేయడానికి మేము పరిమాణం n యొక్క శ్రేణిని ఉపయోగించాము.