სახლის ყაჩაღი Leetcode Solution


Რთული ტური Easy
ხშირად ეკითხებიან Amazon Apple Cisco microsoft Oracle
დინამიური პროგრამირება

პრობლემის განცხადება

ამ პრობლემის დროს ქუჩაში სახლებია და სახლის მძარცველმა უნდა გაძარცოს ეს სახლები. მაგრამ პრობლემა ისაა, რომ მას არ შეუძლია ზედიზედ გაძარცოს ერთზე მეტი სახლი, ანუ რომლებიც ერთმანეთის გვერდით არიან. არა ნეგატიური მთელი რიცხვების ჩამონათვალის გათვალისწინებით, რომლებიც წარმოადგენს თითოეული სახლის ფულის ოდენობას, უნდა გავერკვეთ, თუ რა თანხის მიღება შეუძლია მას.

მაგალითი

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

განმარტება:სახლის ყაჩაღი

გაძარცვეთ სახლი 1 (ფული = 1) და შემდეგ გაძარცვეთ სახლი 3 (ფული = 3).
საერთო თანხა, რომლის გაქურდვაც შეგიძლიათ = 1 + 3 = 4.

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

განმარტება:

Rob სახლი 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 = თანხის ოდენობა მეორე ინდექსების სახლში.

თითოეულ სახლში გვაქვს არჩევანის გაძარცვა ან დატოვება.
საქმე 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) = max (A0, A1).

აქედან გამომდინარე, შეგვიძლია შევაჯამოთ ფორმულა შემდეგნაირად:
f (n) = მაქს (An + f (n-2), f (n-1))

ეს არის რეკურსიული ფორმულა, რომლის განხორციელებაც შეგვიძლია მარტივი რეკურსიის საშუალებით, მაგრამ აქ დროის სირთულე იქნება O (2 ^ n). ამიტომ გამოვიყენებთ დინამიური პროგრამირება მიუახლოვდით და შეინახეთ შუალედური შედეგები მასივში.
გაანგარიშების შემდეგ დავაბრუნებთ მასივში n- (ბოლო) ინდექსში შენახულ მნიშვნელობას.

განხორციელება

C ++ პროგრამა House Robber Leetcode Solution- ისთვის

#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

ჯავა პროგრამა House Robber Leetcode Solution- ისთვის

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

სირთულის ანალიზი House Robber Leetcode Solution- ისთვის

დროის სირთულე

O (n): ჩვენ განმეორებით მივდივართ 1-ლი სახლიდან მე -XNUMX სახლამდე ერთ მარყუჟში, სადაც n არის მთლიანი სახლების რაოდენობა.

სივრცის სირთულე 

O (n): ჩვენ გამოვიყენეთ n ზომის მასივი შუალედური შედეგის შესანახად.