Решение Leetcode для House Robber II


Сложный уровень средний
Часто спрашивают в саман Амазонка Apple eBay Google Microsoft Walmart Labs
Динамическое программирование

В задаче «House Robber II» грабитель хочет украсть деньги из разных домов. Количество денег в домах представлено в виде массива. Нам нужно найти максимальную сумму денег, которую можно заработать, добавив элементы в данный массив в соответствии со следующими условиями:

  1. Грабитель не может ограбить два последовательных дома. То есть мы не можем включить в нашу сумму два последовательных элемента. Если й элемент добавляется к результату, затем (я + 1)й и (я - 1)-й элемент должен быть исключен.
  2. Массив круглый. Итак первый и последний элементы тоже примыкают друг к другу.

Пример

1 5 4 2
7
4 5 6 8 3
13

Подход(Грубая сила)

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

Теперь давайте решим задачу для любого общего линейного массива. Поскольку мы предполагаем, что в массиве отсутствует округлость и он линейный, начиная с первого элемента и заканчивая последним, мы избавились от рассмотрения первого и последнего элементов как смежных.

Теперь ясно, что мы можем либо:

  1. Включают любой элемент в нашей сумме.
  2. Исключать этот элемент.

В таком случае мы можем найти сумму, произведенную всеми возможными последовательностями, имеющими непоследовательные элементы. Чтобы найти все возможные комбинации, мы можем использовать Рекурсия и возврат. В каждом рекурсивном вызове мы либо включаем элемент в нашу сумму результатов, либо исключаем его. Исходя из этого, если мы выберем любой элемент по индексу I, тогда следующий индекс должен быть Я + 2, Я + 3.…. до последнего элемента. Точно так же, если мы исключим элемент по индексу 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

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

Сложность времени

O(№ 2 ^ N), поскольку мы генерируем все возможные подпоследовательности, содержащие непоследовательные элементы.

Пространство сложности

НА) из-за рекурсивных кадров стека

Подход(Динамическое программирование)

В предыдущем подходе мы обсуждали, что при любом конкретном индексе мы можем

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

Решение Leetcode для House Robber II

Предполагать ans [i, N] - максимальная сумма, которую мы можем получить в диапазоне i в N. Этот результат в дальнейшем будет зависеть от ans [i + 2, N] и ans [i + 1, N]. Мы можем рассматривать каждый диапазон как состояние так что каждое состояние дополнительно зависит от подсостояний. Возможно, что нам нужно рекурсивно решать для любого конкретного состояния снова и снова, чтобы решить другие проблемы родительского состояния. Это Оптимальная основа. Мы также можем сделать вывод, что для массива размером 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) Для переменных используется только постоянное пространство.