Решење кућног пљачкаша Леетцоде


Ниво тешкоће Лако
Често питани у амазонка јабука Цисцо мицрософт пророчанство
Динамичко програмирање

Изјава о проблему

У овом проблему постоје куће у улици и кућни пљачкаш мора да их опљачка. Али проблем је што не може узастопно опљачкати више кућа, тј. Које су суседне. С обзиром на листу ненегативних целих бројева који представљају износ новца сваке куће, морамо да сазнамо максималну количину новца коју он може добити.

Пример

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

objašnjenje:Кућни пљачкаш

Опљачкајте кућу 1 (новац = 1), а затим опљачкајте кућу 3 (новац = 3).
Укупан износ који можете опљачкати = 1 + 3 = 4.

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

objašnjenje:

Опљачкајте кућу 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.

Стога, да бисмо решили ову врсту проблема, морамо рекурзивно да претражимо све изборе и из њих изаберемо максимум. Означимо то:

ф (н) = Највећи износ који можете опљачкати од прве куће до н-те индексиране куће.
Аи = Износ новца у и-тој индексној кући.

У свакој кући имамо избор да је опљачкамо или оставимо.
случај 1 - ако изаберемо последњу кућу:
онда не можемо одабрати (н-1) ту кућу, па је стога ф (н) = Ан + ф (н-2)
случај 2 - ако изађемо из последње куће:
онда ћемо се држати максималне добити до (н-1) тх куће, дакле ф (н) = ф (н-1)

Погледајмо основне случајеве.
н = 0, јасно ф (0) = А0.
н = 1, тада је ф (1) = мак (А0, А1).

Стога формулу можемо сумирати на следећи начин:
ф (н) = мак (Ан + ф (н-2), ф (н-1))

Ово је рекурзивна формула коју можемо применити једноставном рекурзијом, али овде ће временска сложеност бити О (2 ^ н). Стога ћемо користити динамичко програмирање приступити и похранити средње резултате у низ.
Након израчунавања вратит ћемо вриједност похрањену у н-том (посљедњем) индексу у низу.

Имплементација

Ц ++ програм за кућно разбојништво Леетцоде решење

#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

Јава програм за Хоусе Роббер Леетцоде решење

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

Анализа сложености кућног разбојника Леетцоде решење

Сложеност времена

На) : вршимо итерацију од 1. куће до н-те куће у једној петљи, где је н број укупних кућа.

Сложеност простора 

На) : користили смо низ величине н за чување средњег резултата.