Решение за куќа арамија Leetcode


Ниво на тешкотија Лесно
Често прашувано во Амазон Јаболко Cisco Мајкрософт Oracle
Динамичко програмирање

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

Во овој проблем има куќи на улица и арамија од куќа мора да ги ограби овие куќи. Но, проблемот е што тој не може да ограби повеќе од една куќа сукцесивно, т.е. кои се соседни едни на други. Со оглед на списокот на ненегативни цели броеви што ја претставуваат количината на пари на секоја куќа, треба да го откриеме максималниот износ на пари што тој може да го добие.

пример

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) = Најголемата сума што можете да ја ограбите од првата куќа до 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) = максимум (A0, A1).

Оттука, можеме да ја сумираме формулата како што следува:
f (n) = максимум (An + f (n-2), f (n-1))

Ова е рекурзивна формула што можеме да ја спроведеме преку едноставна рекурзија, но овде, временската сложеност ќе биде O (2 ^ n). Затоа ќе користиме динамично програмирање пристапи и складирај ги средните резултати во низа.
По пресметувањето, ќе ја вратиме вредноста зачувана во нитиот (последен) индекс во низата.

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

Програма C ++ за решение за арамија од куќа Leetcode

#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

Јава програма за решение за куќа арамија Leetcode

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

Анализа на сложеност за решение за арамија од куќа Leetcode

Временска комплексност

На) : повторуваме од 1-та до втората куќа во една јамка, каде што n е бројот на вкупни куќи.

Комплексноста на просторот 

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