House Robber II Leetcode Solution


Ниво на трудност M
Често задавани в Кирпич Амазонка ябълка иБей Google Microsoft Walmart Labs
Динамично програмиране

В проблема „Разбойник на къщи II“ разбойник иска да ограби пари от различни къщи. Сумата на парите в къщите е представена чрез масив. Трябва да намерим максималната сума пари, която може да бъде направена чрез добавяне на елементите в даден масив според следните условия:

  1. Грабителят не може да ограби нито една поредна къща. Тоест, не можем да включим два последователни елемента в нашата сума. Ако I- след това се добавя елемент към резултата (i + 1)та и (i - 1)този елемент трябва да бъде изключен.
  2. Масивът е кръгъл. Така че първи и последно елемент също са в съседство.

Пример

1 5 4 2
7
4 5 6 8 3
13

Приближаване(Brute Force)

Проблемът изисква да намерим максималната сума, която може да бъде получена чрез добавяне на непоследователни елементи в масива. Можем да пуснем груба сила, за да проверим всяка комбинация от последователности, съдържаща непоследователни елементи. Но индексите 1 и енти всъщност са съседни. Така че, трябва да се уверим, че не включваме и двамата в нашия резултат. Интуитивно можем да намерим максималната сума от подмасив[1, N - 1] и подмасив[2, N] отделно. Сега и двете подредове са линейни. Резултатът ще бъде максимумът от двете суми на подмасива.

Сега, нека решим проблема за всеки общ линеен масив. Тъй като приемаме, че кръгообразността отсъства в масива и тя е линейна, започвайки от първия елемент и завършвайки в последния, ние се отървахме да разглеждаме първия и последния елемент като съседни.

Вече е ясно, че можем:

  1. Включване на всеки елемент в нашата сума.
  2. Изключвам този елемент.

В такъв случай можем да намерим сумата, получена от всички възможни последователности, които имат непоследователни елементи. За да намерим всички възможни комбинации, можем да използваме Рекурсия и Backtracking. Във всяко рекурсивно извикване ние или ще включваме елемента в нашата резултатна сума, или ще го изключим. Въз основа на това, ако изберем който и да е елемент в индекса I, тогава следващият индекс трябва да бъде I + 2, I + 3.…. до последния елемент. По същия начин, ако изключим елемент в индекса I, можем да извикаме следващата рекурсия на индекс I + 1, за да проверите всички възможности, произтичащи от него. По този начин проверяваме възможностите за включване и изключване на всеки елемент. Също така ще бъдат всички елементи, съставляващи сумата непоследователни докато прескачаме до всеки алтернативен индекс.

алгоритъм

  1. Ако масивът е празен, върнете 0;
  2. Ако масивът има един елемент
    • Не можем да разделим масива на две части. И така, върнете единствения елемент в масива
  3. Поддържайте променлива max_sum_possible, която съхранява максималната възможна сума
  4. Извикайте рекурсивна функция комбинации () да се провери за всяка последователност в подмасив [1, N - 1] и [2, N]
    • комбинации ()  има параметър за съхраняване на сумата на всяка подпоследователност като cur_sum
    • Ако сме пресекли последния елемент, ако масивът, се върне.
    • Сега, нека проверим всички възможности, които можем да направим включително и текущата стойност на индекса
      • Добавете текущата стойност на индекса към cur_sum
      • Изпълнете цикъл, започвайки от алтернативния индекс, за да можем да преминем към всеки непоследователен елемент от този индекс
      • Наричам комбинации () по тези индекси
    • Нека проверим възможността, когато текущият елемент не е включен
      • Извадете текущата стойност на индекса от cur_sum, тук ние отстъпление нашето решение
      • Наричам комбинации () на следващия индекс, тъй като изключихме текущия индекс
    • На всяка стъпка проверяваме дали cur_sum> max_sum_possible и го актуализираме
  5. Отпечатайте резултата

Внедряване на алгоритъм за решаване на House Robber II

Програма C ++

#include <bits/stdc++.h>
using namespace std;

void combinations(vector <int> &a , int &cur_sum , int idx , int &end , int &max_sum_possible)
{
    if(idx > end)
        return;


    cur_sum += a[idx];
    if(cur_sum > max_sum_possible)
        max_sum_possible = cur_sum;

    for(int i = idx + 2 ; i <= end ; i++)
        combinations(a , cur_sum , i , end , max_sum_possible);

    cur_sum -= a[idx];
    combinations(a , cur_sum , idx + 1 , end , max_sum_possible);
    return;
}


int rob(vector <int> &a)
{
    int n = a.size();
    if(n == 0)
        return 0;
    if(n == 1)
        return a[0];
    int max_sum_possible = 0 , cur_sum = 0 , end = n - 2;
    combinations(a , cur_sum , 0 , end , max_sum_possible);
    end++;
    combinations(a , cur_sum , 1 , end , max_sum_possible);

    return max_sum_possible;
}

int main()
{
    vector <int> a = {1 , 5 , 4 , 2};
    cout << rob(a) << '\n';
}

Програма Java

import java.lang.Math;


class MutableInt
{
    public int val;
    MutableInt(int x)
    {
        this.val = x;
    }
}


class House_Robber_II
{
    static void combinations(int[] a , int cur_sum , int idx , int end , MutableInt max_sum_possible)
    {
        if(idx > end)
            return;

        cur_sum += a[idx];
        if(cur_sum > max_sum_possible.val)
            max_sum_possible.val = cur_sum;

        for(int i = idx + 2 ; i <= end ; i++)
            combinations(a , cur_sum , i , end , max_sum_possible);

        cur_sum -= a[idx];
        combinations(a , cur_sum , idx + 1 , end , max_sum_possible);
        return;
    }

    static int rob(int[] a)
    {
        int n = a.length;
        if(n == 0)
            return 0;
        if(n == 1)
            return a[0];
        int cur_sum = 0 , end = n - 2;
        MutableInt max_sum_possible = new MutableInt(0);
        combinations(a , cur_sum , 0 , end , max_sum_possible);
        end++;
        combinations(a , cur_sum , 1 , end , max_sum_possible);

        return max_sum_possible.val;
    }
    public static void main(String args[])
    {
        int[] a = {1 , 5 , 4 , 2};
        System.out.println(rob(a));
    }
}

7

Анализ на сложността на решението на House Robber II с Leetcode

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

O(N.2 ^ N), тъй като генерираме всяка възможна подпоследователност, съдържаща непоследователни елементи.

Космическа сложност

НА) поради рекурсивни рамки на стека

Приближаване(Динамично програмиране)

В предишния подход обсъждахме, че при всеки конкретен индекс можем

  • Включване на елемента в нашата сума.
  • Изключвам елемента.

House Robber II Leetcode Solution

предполага, ans [i, N] е максималната сума, която можем да получим в диапазона i да се N. Този резултат допълнително ще зависи от ans [i + 2, N] и ans [i + 1, N]. Можем да разглеждаме всеки диапазон като a са такъв, че всяка държава допълнително зависи от под-държави. Възможно е да се наложи рекурсивно да решаваме за дадено състояние отново и отново, за да решаваме други проблеми на родителското състояние. Това е Оптимална подструктура. Можем също да заключим, че за масив с размер N максималната сума, която може да бъде получена от всички 'n' елементи, е максимумът на тези два резултата:

  • Оптимален резултат, получен до (N - 1) елементи и включително N-ия елемент
  • Най-добър резултат, получен до (N - 1) и с изключение на N-ия елемент

Можем да създадем такава таблица, че таблица [i] съхранява максималната сума, която може да бъде получена с помощта на подмасива [0, i]. Но има два варианта за всеки индекс. И така, трябва да съхраняваме два различни резултата за случаи: когато елементът е включен и когато елементът е изключен.

алгоритъм

  1. Ако масивът е празен, върнете 0
  2. Ако масивът има само един елемент, върнете този елемент
  3. Създайте функция robLinear () който връща максималната сума, която може да бъде получена в линеен масив
  4. robLinear () работи както следва:
    1. Инициирайте две променливи, включени и изключени като 0, който съхранява максималните резултати, които могат да бъдат получени чрез включване и изключване на текущия елемент съответно
    2. При всяка следваща итерация, включен става текущия елемент + изключени резултат от предишен елемент
    3. Изключен става максимумът от включен и изключени резултати от предишния елемент
  5. Върнете максимума от robLinear(1, N - 1) и robLinear(2, N)

Внедряване на алгоритъм за решаване на House Robber II

Програма C ++

#include <bits/stdc++.h>
using namespace std;

int robLinear(int l , int r , vector <int> &a)
{
    int inc = 0 , exc = 0 , temp;

    for(int i = l ; i <= r ; i++)
    {
        temp = max(inc , exc);
        inc = exc + a[i];
        exc = temp;
    }
    return max(inc , exc);
}

int rob(vector <int> &a)
{
    int n = a.size();
    if(n == 0)
        return 0;
    if(n == 1)
        return a[0];
    return max(robLinear(0 , n - 2 , a) , robLinear(1 , n - 1 , a));
}

int main()
{
    vector <int> a = {1 , 5 , 4 , 2};
    cout << rob(a) << '\n';
}

Програма Java

import java.lang.Math;

class House_Robber_II
{
    static int robLinear(int l , int r , int[] a)
    {
        int inc = 0 , exc = 0 , temp;

        for(int i = l ; i <= r ; i++)
        {
            temp = Math.max(inc , exc);
            inc = exc + a[i];
            exc = temp;
        }
        return Math.max(inc , exc);
    }

    static int rob(int[] a)
    {
        int n = a.length;
        if(n == 0)
            return 0;
        if(n == 1)
            return a[0];
        return Math.max(robLinear(0 , n - 2 , a) , robLinear(1 , n - 1 , a));
    }

    public static void main(String args[])
    {
        int[] a = {1 , 5 , 4 , 2};
        System.out.println(rob(a));
    }
}

7

Анализ на сложността при решаване на House Robber II

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

НА), прекосяваме масива 2 пъти. И така, ние правим O (2N) операции, които са линейни.

Космическа сложност

O (1) За променливи се използва само константно пространство.