ஹவுஸ் ராபர் II லீட்கோட் தீர்வு


சிரமம் நிலை நடுத்தர
அடிக்கடி கேட்கப்படுகிறது அடோப் அமேசான் ஆப்பிள் ஈபே கூகிள் மைக்ரோசாப்ட் வால்மார்ட் ஆய்வகங்கள்
டைனமிக் புரோகிராமிங்

“ஹவுஸ் ராபர் II” சிக்கலில், ஒரு கொள்ளையன் வெவ்வேறு வீடுகளில் இருந்து பணத்தை கொள்ளையடிக்க விரும்புகிறான். வீடுகளில் உள்ள பணத்தின் அளவு ஒரு வரிசை மூலம் குறிப்பிடப்படுகிறது. பின்வரும் நிபந்தனைகளுக்கு ஏற்ப கொடுக்கப்பட்ட வரிசையில் உள்ள கூறுகளைச் சேர்ப்பதன் மூலம் செய்யக்கூடிய அதிகபட்ச பணத்தை நாம் கண்டுபிடிக்க வேண்டும்:

  1. கொள்ளையர் தொடர்ந்து இரண்டு வீடுகளையும் கொள்ளையடிக்க முடியாது. அதாவது, எங்கள் தொகையில் தொடர்ச்சியாக இரண்டு கூறுகளை சேர்க்க முடியாது. என்றால் சிருஷ்டிப்பு உறுப்பு முடிவில் சேர்க்கப்படுகிறது, பின்னர் (i + 1)வது மற்றும் (i - 1)உறுப்பு விலக்கப்பட வேண்டும்.
  2. வரிசை வட்டமானது. அதனால் முதல் மற்றும் கடந்த உறுப்பு ஒருவருக்கொருவர் அருகில் உள்ளது.

உதாரணமாக

1 5 4 2
7
4 5 6 8 3
13

அணுகுமுறை (முரட்டு படை)

வரிசையில் தொடர்ச்சியாக அல்லாத கூறுகளைச் சேர்ப்பதன் மூலம் உருவாக்கக்கூடிய அதிகபட்ச தொகையைக் கண்டுபிடிக்க சிக்கல் தேவைப்படுகிறது. தொடர்ச்சியான கூறுகளைக் கொண்ட ஒவ்வொரு வரிசை கலவையையும் சரிபார்க்க நாம் ஒரு முரட்டு சக்தியை இயக்க முடியும். ஆனால், குறியீடுகள் 1st மற்றும் Nth உண்மையில் அருகிலுள்ளவை. எனவே, இவை இரண்டையும் எங்கள் முடிவில் சேர்க்காமல் இருப்பதை உறுதி செய்ய வேண்டும். உள்ளுணர்வாக, சப்ரேயில் இருந்து அதிகபட்ச தொகையை நாம் காணலாம்[1, என் - 1] மற்றும் subarray[2, என்] தனித்தனியாக. இப்போது, ​​இரண்டு சப்ரேக்களும் நேரியல். இதன் விளைவாக இரண்டு துணை-தொகைகளின் அதிகபட்சமாக இருக்கும்.

இப்போது, ​​எந்தவொரு பொது நேரியல் வரிசையிலும் சிக்கலைத் தீர்ப்போம். வரிசையில் சுற்றறிக்கை இல்லை என்றும் அது முதல் உறுப்பிலிருந்து தொடங்கி கடைசியாக முடிவடையும் என்றும் நாம் கருதுவதால், முதல் மற்றும் கடைசி உறுப்புகளை அருகிலுள்ளதாகக் கருதுவதில் இருந்து விடுபட்டுவிட்டோம்.

நம்மால் முடியும் என்பது இப்போது தெளிவாகியுள்ளது:

  1. சேர்க்கிறது எங்கள் தொகையில் எந்த உறுப்பு.
  2. நீக்கவும் அந்த உறுப்பு.

அத்தகைய சந்தர்ப்பத்தில், சாத்தியமான அனைத்து காட்சிகளாலும் உற்பத்தி செய்யப்பட்ட தொகையை நாம் காணலாம் தொடர்ச்சியான கூறுகள். சாத்தியமான அனைத்து சேர்க்கைகளையும் கண்டுபிடிக்க, நாம் பயன்படுத்தலாம் மறுநிகழ்வு மற்றும் பின்னணி. ஒவ்வொரு சுழல்நிலை அழைப்பிலும், எங்கள் முடிவுத் தொகையில் உறுப்பைச் சேர்ப்போம் அல்லது அதை விலக்குவோம். அதன் அடிப்படையில், நாம் குறியீட்டில் எந்த உறுப்புகளையும் தேர்வு செய்தால் I, அடுத்த குறியீடாக இருக்க வேண்டும் நான் + 2, நான் + 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] ஐப் பொறுத்தது. ஒவ்வொரு வரம்பையும் நாம் ஒரு என்று கருதலாம் இருந்து ஒவ்வொரு மாநிலமும் துணை மாநிலங்களைப் பொறுத்தது. பிற பெற்றோர் மாநில பிரச்சினைகளை தீர்க்க எந்தவொரு குறிப்பிட்ட மாநிலத்திற்கும் நாம் மீண்டும் மீண்டும் தீர்வு காண வேண்டும். இது ஒரு உகந்த துணை அமைப்பு. அளவு N இன் வரிசைக்கு, அனைத்து 'n' உறுப்புகளிலிருந்தும் பெறக்கூடிய அதிகபட்ச தொகை இந்த இரண்டு முடிவுகளின் அதிகபட்சம் என்பதையும் நாம் முடிவு செய்யலாம்.

  • உகந்த முடிவு வரை பெறப்பட்டது (என் - 1) கூறுகள் மற்றும் Nth உறுப்பு உட்பட
  • வரை பெறப்பட்ட சிறந்த முடிவு (என் - 1) மற்றும் Nth உறுப்பு தவிர்த்து

நாம் ஒரு அட்டவணையை உருவாக்க முடியும் அட்டவணை [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) செயல்பாடுகளை செய்கிறோம், இது நேரியல்.

விண்வெளி சிக்கலானது

ஓ (1) மாறிகளுக்கு நிலையான இடம் மட்டுமே பயன்படுத்தப்படுகிறது.