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


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

“హౌస్ రాబర్ II” సమస్యలో, ఒక దొంగ వివిధ గృహాల నుండి డబ్బును దోచుకోవాలనుకుంటాడు. ఇళ్ళలోని డబ్బు మొత్తం శ్రేణి ద్వారా సూచించబడుతుంది. కింది షరతుల ప్రకారం ఇచ్చిన శ్రేణిలోని మూలకాలను జోడించడం ద్వారా సంపాదించగల గరిష్ట మొత్తాన్ని మేము కనుగొనాలి:

  1. దొంగ వరుసగా రెండు ఇళ్లను దోచుకోలేడు. అంటే, మన మొత్తంలో వరుసగా రెండు అంశాలను చేర్చలేము. ఉంటే ith మూలకానికి ఫలితానికి జోడించబడుతుంది (i + 1)వ మరియు (i - 1)వ మూలకాన్ని తప్పక మినహాయించాలి.
  2. శ్రేణి వృత్తాకారంగా ఉంటుంది. కాబట్టి, ది మొదటి మరియు గత మూలకం ఒకదానికొకటి ప్రక్కనే ఉన్నాయి.

ఉదాహరణ

1 5 4 2
7
4 5 6 8 3
13

అప్రోచ్ (బ్రూట్ ఫోర్స్)

శ్రేణిలో వరుసగా కాని మూలకాలను జోడించడం ద్వారా ఉత్పత్తి చేయగల గరిష్ట మొత్తాన్ని కనుగొనడం సమస్యకు అవసరం. వరుస-కాని అంశాలను కలిగి ఉన్న ప్రతి శ్రేణి కలయికను తనిఖీ చేయడానికి మేము బ్రూట్ ఫోర్స్‌ని అమలు చేయవచ్చు. కానీ, సూచికలు 1st మరియు n వ నిజానికి ప్రక్కనే ఉన్నాయి. కాబట్టి, ఈ రెండింటినీ మా ఫలితంలో చేర్చకుండా చూసుకోవాలి. అకారణంగా, మేము సబ్‌రే నుండి గరిష్ట మొత్తాన్ని కనుగొనవచ్చు[1, ఎన్ - 1] మరియు సబ్‌రే[2, ఎన్] విడిగా. ఇప్పుడు, రెండు సబ్‌రేలు సరళంగా ఉన్నాయి. ఫలితం రెండు సబ్‌రే-మొత్తాలలో గరిష్టంగా ఉంటుంది.

ఇప్పుడు, ఏదైనా సాధారణ సరళ శ్రేణికి సమస్యను పరిష్కరిద్దాం. వృత్తాకార శ్రేణిలో లేదని మరియు ఇది మొదటి మూలకం నుండి మొదలై చివరిలో ముగుస్తుందని మేము As హించినట్లుగా, మొదటి మరియు చివరి మూలకాన్ని ప్రక్కనే పరిగణించకుండా వదిలించుకున్నాము.

మనం గాని చేయగలమని ఇప్పుడు స్పష్టమైంది:

  1. చేర్చండి మా మొత్తంలో ఏదైనా మూలకం.
  2. మినహాయించాలని ఆ మూలకం.

అటువంటప్పుడు, సాధ్యమయ్యే అన్ని సన్నివేశాల ద్వారా ఉత్పత్తి చేయబడిన మొత్తాన్ని మనం కనుగొనవచ్చు వరుస కాని అంశాలు. సాధ్యమయ్యే అన్ని కలయికలను కనుగొనడానికి, మేము ఉపయోగించవచ్చు పునరావృతం మరియు బ్యాక్‌ట్రాకింగ్. ప్రతి పునరావృత కాల్‌లో, మేము మా ఫలిత మొత్తంలో మూలకాన్ని చేర్చుతాము లేదా దానిని మినహాయించాము. దాని ఆధారంగా, మేము ఇండెక్స్ వద్ద ఏదైనా మూలకాన్ని ఎంచుకుంటే I, తదుపరి సూచిక ఉండాలి I + 2, I + 3.…. చివరి మూలకం వరకు. అదేవిధంగా, మేము ఇండెక్స్ వద్ద ఒక మూలకాన్ని మినహాయించినట్లయితే I, మేము ఇండెక్స్లో తదుపరి పునరావృత్తిని పిలుస్తాము నేను + 1, దాని నుండి ఉద్భవించే అన్ని అవకాశాలను తనిఖీ చేయడానికి. ఈ విధంగా, ప్రతి మూలకాన్ని చేర్చడానికి మరియు మినహాయించే అవకాశాలను మేము తనిఖీ చేస్తాము. అలాగే, మొత్తాన్ని కలిగి ఉన్న అన్ని అంశాలు ఉంటాయి వరుసగా కాదు మేము ప్రతి ప్రత్యామ్నాయ సూచికకు దూకుతున్నప్పుడు.

అల్గారిథం

  1. శ్రేణి ఖాళీగా ఉంటే, తిరిగి వెళ్ళు 0;
  2. శ్రేణికి ఒక మూలకం ఉంటే
    • మేము శ్రేణిని రెండు భాగాలుగా విభజించలేము. కాబట్టి, శ్రేణిలోని ఏకైక మూలకాన్ని తిరిగి ఇవ్వండి
  3. Max_sum_possible అనే వేరియబుల్‌ను నిర్వహించండి, ఇది గరిష్ట మొత్తాన్ని నిల్వ చేస్తుంది
  4. కాల్ పునరావృత ఫంక్షన్ కలయికలు () సబ్‌రే [1, N - 1] మరియు [2, N]
    • కలయికలు ()  ప్రతి తదుపరి మొత్తాన్ని నిల్వ చేయడానికి పరామితిని కలిగి ఉంటుంది cur_sum
    • శ్రేణి ఉంటే మేము చివరి మూలకాన్ని దాటితే, తిరిగి.
    • ఇప్పుడు, మనం చేయగల అన్ని అవకాశాలను తనిఖీ చేద్దాం సహా పార్టీ ప్రస్తుత సూచిక విలువ
      • ప్రస్తుత సూచిక విలువను జోడించండి cur_sum
      • ప్రత్యామ్నాయ సూచిక నుండి ప్రారంభమయ్యే లూప్‌ను అమలు చేయండి, తద్వారా ఈ సూచిక నుండి వరుసగా కాని ప్రతి మూలకానికి మనం వెళ్ళవచ్చు
      • కాల్ కలయికలు () ఈ సూచికలపై
    • ప్రస్తుత మూలకం చేర్చబడనప్పుడు అవకాశాన్ని తనిఖీ చేద్దాం
      • ప్రస్తుత సూచిక విలువను cur_sum నుండి తీసివేయండి, ఇక్కడ మేము వ్యతిరేకదిశలో చలించు మా పరిష్కారం
      • కాల్ కలయికలు () ప్రస్తుత సూచికలో, మేము ప్రస్తుత సూచికను మినహాయించాము
    • అడుగడుగునా, మేము cur_sum> max_sum_possible అని తనిఖీ చేసి దాన్ని అప్‌డేట్ చేస్తాము
  5. ఫలితాన్ని ముద్రించండి

హౌస్ రాబర్ II ను పరిష్కరించడానికి అల్గోరిథం అమలు

సి ++ ప్రోగ్రామ్

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

void combinations(vector <int> &a , int &cur_sum , int idx , int &end , int &max_sum_possible)
{
    if(idx > end)
        return;


    cur_sum += a[idx];
    if(cur_sum > max_sum_possible)
        max_sum_possible = cur_sum;

    for(int i = idx + 2 ; i <= end ; i++)
        combinations(a , cur_sum , i , end , max_sum_possible);

    cur_sum -= a[idx];
    combinations(a , cur_sum , idx + 1 , end , max_sum_possible);
    return;
}


int rob(vector <int> &a)
{
    int n = a.size();
    if(n == 0)
        return 0;
    if(n == 1)
        return a[0];
    int max_sum_possible = 0 , cur_sum = 0 , end = n - 2;
    combinations(a , cur_sum , 0 , end , max_sum_possible);
    end++;
    combinations(a , cur_sum , 1 , end , max_sum_possible);

    return max_sum_possible;
}

int main()
{
    vector <int> a = {1 , 5 , 4 , 2};
    cout << rob(a) << '\n';
}

జావా ప్రోగ్రామ్

import java.lang.Math;


class MutableInt
{
    public int val;
    MutableInt(int x)
    {
        this.val = x;
    }
}


class House_Robber_II
{
    static void combinations(int[] a , int cur_sum , int idx , int end , MutableInt max_sum_possible)
    {
        if(idx > end)
            return;

        cur_sum += a[idx];
        if(cur_sum > max_sum_possible.val)
            max_sum_possible.val = cur_sum;

        for(int i = idx + 2 ; i <= end ; i++)
            combinations(a , cur_sum , i , end , max_sum_possible);

        cur_sum -= a[idx];
        combinations(a , cur_sum , idx + 1 , end , max_sum_possible);
        return;
    }

    static int rob(int[] a)
    {
        int n = a.length;
        if(n == 0)
            return 0;
        if(n == 1)
            return a[0];
        int cur_sum = 0 , end = n - 2;
        MutableInt max_sum_possible = new MutableInt(0);
        combinations(a , cur_sum , 0 , end , max_sum_possible);
        end++;
        combinations(a , cur_sum , 1 , end , max_sum_possible);

        return max_sum_possible.val;
    }
    public static void main(String args[])
    {
        int[] a = {1 , 5 , 4 , 2};
        System.out.println(rob(a));
    }
}

7

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

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

O(N.2 ^ N.) మేము వరుసగా కాని మూలకాలను కలిగి ఉన్న ప్రతి తదుపరి ఉత్పత్తిని ఉత్పత్తి చేస్తున్నప్పుడు.

స్థల సంక్లిష్టత

పై) పునరావృత స్టాక్ ఫ్రేమ్‌ల కారణంగా

అప్రోచ్ (డైనమిక్ ప్రోగ్రామింగ్)

మునుపటి విధానంలో ఏదైనా ప్రత్యేకమైన సూచికలో, మనం చేయగలమని చర్చించాము

  • చేర్చండి మా మొత్తంలో మూలకం.
  • మినహాయించాలని మూలకం.

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

భావించండి ans [i, N] మేము పరిధిలో పొందగల గరిష్ట మొత్తం i కు N. ఈ ఫలితం ans [i + 2, N] మరియు ans [i + 1, N] పై ఆధారపడి ఉంటుంది. మేము ప్రతి పరిధిని a గా పరిగణించవచ్చు రాష్ట్ర ప్రతి రాష్ట్రం ఉప రాష్ట్రాలపై ఆధారపడి ఉంటుంది. ఇతర మాతృ రాష్ట్ర సమస్యలను పరిష్కరించడానికి మనం ఏదైనా నిర్దిష్ట రాష్ట్రం కోసం మళ్లీ మళ్లీ పరిష్కరించాల్సిన అవసరం ఉంది. ఇది ఒక ఆప్టిమల్ సబ్‌స్ట్రక్చర్. పరిమాణం N యొక్క శ్రేణి కోసం, అన్ని 'n' మూలకాల నుండి పొందగలిగే గరిష్ట మొత్తం ఈ రెండు ఫలితాల గరిష్టమని మేము నిర్ధారించగలము:

  • సరైన ఫలితం (ఎన్ - 1) అంశాలు మరియు N వ మూలకంతో సహా
  • వరకు ఉత్తమ ఫలితం పొందబడింది (ఎన్ - 1) మరియు N వ మూలకాన్ని మినహాయించి

మేము అలాంటి పట్టికను సృష్టించవచ్చు పట్టిక [i] సబ్‌రే [0, i] ఉపయోగించి పొందగలిగే గరిష్ట మొత్తాన్ని నిల్వ చేస్తుంది. కానీ, ప్రతి సూచికకు రెండు ఎంపికలు ఉన్నాయి. కాబట్టి, కేసుల కోసం మేము రెండు వేర్వేరు ఫలితాలను నిల్వ చేయాలి: మూలకం చేర్చబడినప్పుడు మరియు మూలకం మినహాయించినప్పుడు.

అల్గారిథం

  1. శ్రేణి ఖాళీగా ఉంటే, 0 తిరిగి ఇవ్వండి
  2. శ్రేణికి కేవలం ఒక మూలకం ఉంటే, ఆ మూలకాన్ని తిరిగి ఇవ్వండి
  3. ఒక ఫంక్షన్ సృష్టించండి robLinear () ఇది సరళ శ్రేణిలో పొందగల గరిష్ట మొత్తాన్ని అందిస్తుంది
  4. robLinear () ఈ క్రింది విధంగా పనిచేస్తుంది:
    1. చేర్చబడిన మరియు మినహాయించిన రెండు వేరియబుల్స్ ప్రారంభించండి 0, ఇది ప్రస్తుత మూలకాన్ని వరుసగా చేర్చడం మరియు మినహాయించడం ద్వారా పొందగలిగే గరిష్ట ఫలితాలను నిల్వ చేస్తుంది
    2. ప్రతి తదుపరి పునరావృతంలో, చేర్చబడినది ప్రస్తుత మూలకం + అవుతుంది మినహాయించాలి మునుపటి మూలకం ఫలితం
    3. మినహాయించబడినది గరిష్టంగా అవుతుంది చేర్చబడిన మరియు మినహాయించాలి మునుపటి మూలకం యొక్క ఫలితాలు
  5. రాబ్‌లినియర్ యొక్క గరిష్టాన్ని తిరిగి ఇవ్వండి(1, ఎన్ - 1) మరియు రాబ్ లీనియర్(2, ఎన్)

హౌస్ రాబర్ II ను పరిష్కరించడానికి అల్గోరిథం అమలు

సి ++ ప్రోగ్రామ్

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

int robLinear(int l , int r , vector <int> &a)
{
    int inc = 0 , exc = 0 , temp;

    for(int i = l ; i <= r ; i++)
    {
        temp = max(inc , exc);
        inc = exc + a[i];
        exc = temp;
    }
    return max(inc , exc);
}

int rob(vector <int> &a)
{
    int n = a.size();
    if(n == 0)
        return 0;
    if(n == 1)
        return a[0];
    return max(robLinear(0 , n - 2 , a) , robLinear(1 , n - 1 , a));
}

int main()
{
    vector <int> a = {1 , 5 , 4 , 2};
    cout << rob(a) << '\n';
}

జావా ప్రోగ్రామ్

import java.lang.Math;

class House_Robber_II
{
    static int robLinear(int l , int r , int[] a)
    {
        int inc = 0 , exc = 0 , temp;

        for(int i = l ; i <= r ; i++)
        {
            temp = Math.max(inc , exc);
            inc = exc + a[i];
            exc = temp;
        }
        return Math.max(inc , exc);
    }

    static int rob(int[] a)
    {
        int n = a.length;
        if(n == 0)
            return 0;
        if(n == 1)
            return a[0];
        return Math.max(robLinear(0 , n - 2 , a) , robLinear(1 , n - 1 , a));
    }

    public static void main(String args[])
    {
        int[] a = {1 , 5 , 4 , 2};
        System.out.println(rob(a));
    }
}

7

హౌస్ దొంగ II ను పరిష్కరించే సంక్లిష్టత విశ్లేషణ

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

పై), మేము శ్రేణిని 2 సార్లు ప్రయాణించాము. కాబట్టి, మేము O (2N) ఆపరేషన్లను చేస్తాము, ఇది సరళంగా ఉంటుంది.

స్థల సంక్లిష్టత

O (1) వేరియబుల్స్ కోసం స్థిరమైన స్థలం మాత్రమే ఉపయోగించబడుతుంది.