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


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

פּראָבלעם סטאַטעמענט  

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

בייַשפּיל

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.

צוגאַנג  

דעם פּראָבלעם קענען ניט זיין סאַלווד דורך זשעדנע צוגאַנג.
לאָמיר נעמען אַ ביישפּיל:
נומס = [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) = די גרעסטע סומע וואָס איר קענען באַגאַזלענען פֿון דער ערשטער הויז צו די ינדעקסט הויז.
אַי = סומע פון ​​געלט אין די אינדעקס הויז.

זע אויך
מבול פּלאָמבירן לעעטקאָדע

ביי יעדער הויז מיר האָבן די ברירה פון ראַבינג עס אָדער לאָזן עס.
פאַל 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))

דאָס איז אַ רעקורסיווע פאָרמולע וואָס מיר קענען ימפּלאַמענטאַד דורך פּשוט רעקורסיאָן, אָבער די צייט קאַמפּלעקסיטי איז אָ (2 ^ n). דעריבער מיר וועלן נוצן דינאַמיש פּראָגראַממינג צוגאַנג און קראָם די ינטערמידייט רעזולטאַטן אין אַ מענגע.
נאָך קאַלקיאַלייטינג, מיר וועלן צוריקקומען די ווערט סטאָרד אין די נט (אינדעקס) אינדעקס אין מענגע.

ימפּלעמענטאַטיאָן  

C ++ פּראָגראַם פֿאַר הויז ראַבער לעעטקאָדע סאַלושאַן

#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

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

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

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

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

אָ (n): מיר זענען יטעראַטינג פון 1 הויז צו XNUMX טה הויז אין אַ איין שלייף, ווו N איז די נומער פון גאַנץ הייזער.

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

אָ (n): מיר האָבן געוויינט אַ מענגע פון ​​גרייס N צו קראָם די ינטערמידייט רעזולטאַט.