Рішення для домашніх грабіжників Leetcode


Рівень складності Легко
Часто запитують у Амазонка Apple Cisco Microsoft оракул
Динамічне програмування

Постановка проблеми

У цій проблемі є будинки на вулиці, і Грабіжник домів повинен пограбувати ці будинки. Але проблема в тому, що він не може пограбувати послідовно більше одного будинку, тобто сусідніх один з одним. Враховуючи список невід’ємних цілих чисел, що представляють суму грошей кожного будинку, ми повинні з’ясувати максимальну суму грошей, яку він може отримати.

Приклад

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.

Підхід

Цю проблему не можна вирішити жадібним підходом.
Візьмемо приклад:
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 = Кількість грошей у i-му індексному будинку.

У кожному будинку ми маємо можливість пограбувати його або залишити.
випадок 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) = max (An + f (n-2), f (n-1))

Це рекурсивна формула, яку ми можемо реалізувати за допомогою простої рекурсії, але тут складність часу буде O (2 ^ n). Тому будемо використовувати динамічне програмування підходити і зберігати проміжні результати в масиві.
Після обчислення ми повернемо значення, збережене в n-му (останньому) індексі в масиві.

Реалізація

Програма C ++ для рішення хатнього розбійника 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

Програма Java для домашнього розбійника 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

Аналіз складності рішення для розбійників домашніх літкодів

Складність часу

O (n): ми виконуємо ітерацію від 1-го будинку до n-го будинку в одному циклі, де n - загальна кількість будинків.

Складність простору 

O (n): ми використали масив розміром n для зберігання проміжного результату.