הויז ראַבער וו לעעטקאָדע סאַלושאַן  


שוועריקייט לעוועל מיטל
אָפט געבעטן אין אַדאָובי אַמאַזאָן עפּל עבייַ גוגל מייקראָסאָפֿט וואַלמאַרט לאַבס
אַלגערידאַמז קאָדירונג דינאַמיש פּראָגראַממינג אינטערוויו interviewprep LeetCode LeetCodeSolutions

אין די "הויז ראַבער וו" פּראָבלעם, אַ גאַזלן וויל צו באַגאַזלענען געלט פון פאַרשידענע הייזער. די סומע פון ​​געלט אין די הייזער איז רעפּריזענטיד דורך אַ מענגע. מיר דאַרפֿן צו געפֿינען די מאַקסימום סומע פון ​​געלט וואָס קענען זיין געמאכט דורך אַדינג די עלעמענטן אין אַ געגעבן מענגע לויט די פאלגענדע באדינגונגען:

  1. דער גזלן קען נישט בארויבן קיין צוויי קאָנסעקוטיווע הייזער. דאָס איז, מיר קענען נישט אַרייַננעמען צוויי קאָנסעקוטיווע עלעמענטן אין אונדזער סומע. אויב די יטה דער עלעמענט איז מוסיף צו דער רעזולטאַט (איך + 1)סטן און (איך - 1)דער עלעמענט מוזן זיין יקסקלודיד.
  2. די מענגע איז קייַלעכיק. אַזוי, די ערשטער און לעצט עלעמענט זענען שכייניש צו יעדער אנדערער אויך.

בייַשפּיל  

1 5 4 2
7
4 5 6 8 3
13

צוגאַנג (ברוט פאָרס 

די פּראָבלעם דאַרף מיר געפֿינען די מאַקסימום סומע וואָס קענען זיין געשאפן דורך אַדינג ניט-קאָנסעקוטיווע עלעמענטן אין דעם מענגע. מיר קענען פירן אַ ברוטע קראַפט צו קאָנטראָלירן יעדער סיקוואַנס קאָמבינאַציע מיט ניט-קאָנסעקוטיווע עלעמענטן. אָבער, די ינדאַסיז קסנומקססט און נט זענען אַקשלי שכייניש. מיר מוזן ענשור אַז זיי ביידע ניט אַרייַננעמען אין אונדזער רעזולטאַט. ינטויטיוועלי, מיר קענען געפֿינען די מאַקסימום סומע פון ​​סובאַרראַי[1, N - 1] און סובאַרראַי[2, N] באַזונדער. איצט, די סובאַררייַס זענען לינעאַר. דער רעזולטאַט וועט זיין די מאַקסימום פון די צוויי סובאַרראַי-סאַמז.

זע אויך
פליסנדיק סומע פון ​​1 ד עריי לעעטקאָדע לייזונג

לאָמיר סאָלווע די פּראָבלעם פֿאַר אַ גענעראַל לינעאַר מענגע. ווי מיר יבערנעמען אַז די סירקולאַריטי איז ניטאָ אין די מענגע און עס איז לינעאַר סטאַרטינג פון דער ערשטער עלעמענט און ענדיקן די לעצטע, מיר האָבן באַקומען באַפרייַען פון באַטראַכטן ערשטער און לעצט עלעמענט ווי שכייניש.

עס איז איצט קלאָר אַז מיר קענען:

  1. אַרייַננעמען קיין עלעמענט אין אונדזער סומע.
  2. ויסשליסן אַז עלעמענט.

אין אַזאַ אַ פאַל, מיר קענען געפֿינען די סומע געשאפן דורך אַלע מעגלעך סיקוואַנסיז ניט-קאָנסעקוטיווע עלעמענטן. מיר קענען נוצן אַלע מעגלעך קאַמבאַניישאַנז רעקורסיאָן און באַקקטראַקקינג. אין יעדער רעקורסיווע רוף, מיר וועלן אַרייַן די עלעמענט אין אונדזער רעזולטאַט סומע אָדער ויסשליסן עס. באַזירט אויף דעם, אויב מיר קלייַבן אַן עלעמענט אין דער אינדעקס I, דער ווייַטער אינדעקס זאָל זיין איך + 2, איך + 3.…. ביז די לעצטע עלעמענט. סימילאַרלי, אויב מיר ויסשליסן אַן עלעמענט אין אינדעקס I, מיר קענען רופן ווייַטער רעקורסיאָן אויף אינדעקס איך + 1, צו קאָנטראָלירן אַלע פּאַסאַבילאַטיז פון עס. אויף דעם וועג, מיר קאָנטראָלירן די פּאַסאַבילאַטיז צו אַרייַננעמען און ויסשליסן יעדער עלעמענט. אַלע יסודות וואָס זייַנען די סומע וועט זיין ניט-קאָנסעקוטיווע ווען מיר שפּרינגען צו יעדער אנדערער אינדעקס.

אַלגאָריטהם

  1. אויב די מענגע איז ליידיק, צוריקקומען ;
  2. אויב די מענגע האט איין עלעמענט
    • מיר קענען נישט צעטיילן די מענגע אין צוויי פּאַרץ. אַזוי, צוריקקומען די בלויז עלעמענט אין די מענגע
  3. טייַנען אַ בייַטעוודיק, max_sum_possible, וואָס סטאָרז די מאַקסימום סומע
  4. רוף רעקורסיווע פונקציע קאַמבאַניישאַנז () צו קאָנטראָלירן פֿאַר יעדער סאַבסאַקוואַנס אין סובאַררייַ [1, N - 1] און [2, N]
    • קאַמבאַניישאַנז ()  האט פּאַראַמעטער צו קראָם די סומע פון ​​יעדער סאַבסטאַנסאַז ווי cur_sum
    • אויב מיר האָבן אַריבער די לעצטע עלעמענט אויב די מענגע, צוריקקומען.
    • איצט לאָזן אונדז קאָנטראָלירן אַלע פּאַסאַבילאַטיז כולל די קראַנט אינדעקס ווערט
      • לייג קראַנט אינדעקס ווערט צו cur_sum
      • לויפן אַ שלייף סטאַרטינג פון די אָלטערנאַטיוו אינדעקס אַזוי אַז מיר קענען שפּרינגען צו יעדער ניט-קאָנסעקוטיווע עלעמענט פֿון דעם אינדעקס
      • רוף קאַמבאַניישאַנז () אויף די ינדאַסיז
    • זאל ס קאָנטראָלירן די מעגלעכקייט ווען די קראַנט עלעמענט איז נישט אַרייַנגערעכנט
      • אַראָפּרעכענען קראַנט אינדעקס ווערט פון cur_sum, דאָ מיר באַקטראַק אונדזער לייזונג
      • רוף קאַמבאַניישאַנז () אויף ווייַטער אינדעקס, ווייַל מיר האָבן יקסקלודיד קראַנט אינדעקס
    • אין יעדער שריט, מיר קאָנטראָלירן אויב cur_sum> max_sum_possible און דערהייַנטיקן עס
  5. דרוק דעם רעזולטאַט
זע אויך
שטריקל וואָס ריכטן זיך אין אַן Array Leetcode לייזונג

ימפּלאַמענטיישאַן פון אַלגערידאַם צו סאָלווע הויז ראַבער וו

C ++ פּראָגראַם

#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';
}

Java פּראָגראַם

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

קאַמפּלעקסיטי אַנאַליסיס פון הויז ראַבער וו לעעטקאָדע סאַלושאַן

צייט קאַמפּלעקסיטי

O(N.2 ^ Nווי מיר דזשענערייט יעדער מעגלעך סאַבסטאַנסאַז מיט ניט-קאָנסעקוטיווע עלעמענטן.

אָרט קאַמפּלעקסיטי

אָ (N) רעכט צו רעקורסיווע אָנלייגן ראָמען

צוגאַנג (דינאַמיש פּראָגראַממינג 

מיר האָבן דיסקאַסט אין דעם פריערדיקן צוגאַנג אַז מיר קענען ביי קיין ספּעציעלע אינדעקס

  • אַרייַננעמען די עלעמענט אין אונדזער סאַכאַקל.
  • ויסשליסן דער עלעמענט.
זע אויך
ויסמעקן מיטל עלעמענט פון אַ אָנלייגן

הויז ראַבער וו לעעטקאָדע סאַלושאַןשפּילקע

יבערנעמען אַנס [i, N] איז די מאַקסימום סומע וואָס מיר קענען דערגרייכן אין די קייט i צו N. דער רעזולטאַט וועט ווייטער אָפענגען אויף ans [i + 2, N] און ans [i + 1, N]. מיר קענען באַטראַכטן יעדער קייט ווי אַ זענען אַזאַ אַז יעדער שטאַט איז ווייטער דעפּענדס אויף סאַב-שטאַטן. עס איז מעגלעך אַז מיר דאַרפֿן צו רעקורסיוועלי סאָלווע פֿאַר אַ באַזונדער שטאַט ווידער און ווידער צו סאָלווע אנדערע עלטערן שטאַט פּראָבלעמס. דאָס איז אַן אָפּטימאַל סובסטרוקטורע. מיר קענען אויך פאַרענדיקן אַז פֿאַר אַ מענגע פון ​​גרייס N, די מאַקסימום סומע וואָס קען זיין באקומען פון אַלע 'n' עלעמענטן איז די מאַקסימום פון די צוויי רעזולטאַטן:

  • אָפּטימאַל רעזולטאַט באקומען ביז (N - 1) עלעמענטן און כולל די Nth עלעמענט
  • בעסטער רעזולטאַט באקומען ביז (N - 1) און עקסקלודינג די Nth עלעמענט

מיר קענען מאַכן אַ טיש אַזאַ ווי טיש [איך] סטאָרז די מאַקסימום סומע וואָס קענען זיין באקומען מיט די סובאַרראַי [0, איך]. אָבער, עס זענען צוויי ברירות פֿאַר יעדער אינדעקס. מיר דאַרפֿן צו קראָם צוויי פאַרשידענע רעזולטאַטן פֿאַר קאַסעס: ווען דער עלעמענט איז אַרייַנגערעכנט און ווען דער עלעמענט איז יקסקלודיד.

אַלגאָריטהם

  1. אויב די מענגע איז ליידיק, צוריקקומען 0
  2. אויב די מענגע האט בלויז איין עלעמענט, צוריקקומען דעם עלעמענט
  3. שאַפֿן אַ פֿונקציע robLinear () אַז קערט די מאַקסימום סומע וואָס קענען זיין באקומען אין אַ לינעאַר מענגע
  4. robLinear () אַרבעט ווי גייט:
    1. אָנהייבן צוויי וועריאַבאַלז אַרייַנגערעכנט און יקסקלודיד ווי 0, וואָס סטאָרז די מאַקסימום רעזולטאַטן וואָס זענען באקומען דורך ינקלודז און עקסקלודינג די קראַנט עלעמענט ריספּעקטיוולי
    2. ביי יעדער ווייַטער יטעראַטיאָן, ינקלודעד ווערט די קראַנט עלעמענט + יקסקלודיד רעזולטאַט פון פרייַערדיק עלעמענט
    3. יקסקלודיד ווערט די מאַקסימום פון אַרייַנגערעכנט און יקסקלודיד רעזולטאַטן פון פריערדיקן עלעמענט
  5. ווייַזן די מאַקסימום פון ראָבלינעאַר(1, ען - 1) און ראָבלינאַר(2, ען)
זע אויך
לימענאַד טשאַנגע לעעטקאָדע סאַלושאַן

ימפּלאַמענטיישאַן פון אַלגערידאַם צו סאָלווע הויז ראַבער וו

C ++ פּראָגראַם

#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';
}

Java פּראָגראַם

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

קאַמפּלעקסיטי אַנאַליסיס פון סאַלווינג הויז ראַבער וו

צייט קאַמפּלעקסיטי

אָ (N), מיר דורכפאָר די מענגע פֿאַר 2 מאָל. אַזוי מיר מאַכן אָ (2 ן) אַפּעריישאַנז, וואָס איז לינעאַר.

אָרט קאַמפּלעקסיטי

אָ (1) בלויז קעסיידערדיק פּלאַץ איז געניצט פֿאַר וועריאַבאַלז.