House Robber

Q: Какова рекуррентная формула для задачи «Дом грабителей»?

Наибольшая сумма для первых k домов — это max(best[k-1], best[k-2] + nums[k-1]) . Вы либо пропускаете дом k-1 и сохраняете наибольшую сумму для домов до него, либо берёте дом k-1 и прибавляете его стоимость к наибольшей сумме для домов до соседнего с ним. Базовые случаи: 0 домов и nums[0] для одного дома.

Q: Почему выбор каждого второго дома не решает задачу «Домушник»?

В лучшем плане иногда пропускаются два дома подряд. В [10, 1, 1, 10] сумма чётных домов и сумма нечётных домов равны 11, а если взять первый и последний дом, получится 20. Динамическое программирование сравнивает варианты пропустить дом и взять его для каждого дома, поэтому находит такие планы.

СреднеДинамическое программирование

+10

Дома стоят в ряд вдоль улицы, а nums[i] — это сумма денег в доме i. Ты можешь взять деньги из любых домов на свой выбор, но никогда не бери деньги из двух домов, стоящих рядом. Верни наибольшую сумму, которую можешь взять.

Функция

rob(nums: integer-array) → integer

numsinteger-array: сумма денег в каждом доме в порядке следования по улице
Возвращаетinteger: наибольшая сумма, которую можно получить, не забирая деньги из двух соседних домов

Ограничения

1 ≤ nums.length ≤ 10⁴
0 ≤ nums[i] ≤ 1000
Ответ не превышает 5 × 10⁶, поэтому он помещается в знаковое 32-битное целое число.

Примеры

Ввод: nums = [5, 3, 4, 11, 2]
Вывод: 16
Пояснение: Возьми 5 и 11 из домов 0 и 3, чтобы получить 16. Можно пропустить два дома подряд, и в этом случае такой вариант лучше всех остальных: 5 + 4 + 2 = 11 и 3 + 11 = 14.

+16 скрытых тестов при отправке

Дополнительный вопрос

Верни дома, которые нужно забрать, а также общую сумму. Что нужно сохранить из таблицы, чтобы восстановить этот список, и смогут ли два текущих итога по-прежнему это сделать?

Подсказки

Открывайте по одной. Каждая подсказывает чуть больше.

Открыто 0 из 3

Решение

Очевидные упрощённые решения не работают. Если брать каждый второй дом, можно пропустить варианты, в которых пропускаются два дома подряд, например 5 и 11 в [5, 3, 4, 11, 2]. А если сначала брать самый богатый дом, это не сработает для [3, 4, 3], где дом со стоимостью 4 перекрывает два дома, вместе стоящих 6. Работает другой подход: принимать решение для каждого дома по очереди. Лучшая сумма для домов вплоть до текущего зависит только от лучших сумм для домов, расположенных за два дома до него.

Попробуй оба варианта у каждого дома

Верно, но не успевает на самых больших тестах

Идея

Посмотри на последний дом, дом n-1. Любой план либо пропускает его, либо выбирает. Если он его пропускает, лучшее, что можно сделать, — это выбрать лучший план для первых n-1 домов. Если он его выбирает, дом n-2 становится недоступен, поэтому к лучшему плану для первых n-2 домов прибавляется nums[n-1]. Ответ — большее из этих двух значений.

Запишем это в виде функции most(k) — максимального количества, которое можно взять из первых k домов: most(k) = max(most(k-1), most(k-2) + nums[k-1]), где most(0) = 0 для случая без домов и most(1) = nums[0] для одного дома. Любой план либо пропускает последний дом, либо выбирает его, поэтому эти две ветви охватывают все планы, и результат верен.

Это работает медленно из-за перекрытия ветвей. most(k-1) снова вызывает most(k-2), поэтому один и тот же вопрос решается снова и снова, а число вызовов растёт как числа Фибоначчи — примерно как 1.6^n. Для сорока домов уже требуется более 300 миллионов вызовов, а в тестах бывает до 10^4 домов. Кроме того, вызовы вкладываются на глубину n уровней, превышая установленный в Python по умолчанию предел в 1000.

Алгоритм

Напишите вспомогательную функцию most(k), которая возвращает максимальную сумму, которую можно получить из первых k домов.
Возвращайте 0, если k равно 0, и nums[0], если k равно 1.
В противном случае вычислите skip = most(k-1) и take = most(k-2) + nums[k-1].
Возвращайте большее из двух значений. Ответ — most(n).

def rob(nums):
    def most(k):
        # The most you can take from the first k houses
        if k == 0:
            return 0
        if k == 1:
            return nums[0]
        # Skip house k-1, or take it and skip house k-2
        return max(most(k - 1), most(k - 2) + nums[k - 1])

    return most(len(nums))

Таблица снизу вверх

Идея

Рекурсия задаёт вопросы только о most(0) — most(n), поэтому есть n + 1 разных вопросов. Ответь на каждый из них один раз, сохрани его в таблице и заполняй таблицу в таком порядке, чтобы каждый ответ, который ты читаешь, уже был в ней. Таблицу определяют четыре решения.

Состояние: best[k] — это максимальная сумма, которую можно получить, взяв деньги из первых k домов. Рекуррентное соотношение: best[k] = max(best[k-1], best[k-2] + nums[k-1]): пропустить дом k-1 или взять деньги из него, прибавив их к максимуму для домов до его соседа. Базовые случаи: best[0] = 0 и best[1] = nums[0]. Порядок: перебирай k от 2 до n, потому что каждая запись использует две предыдущие.

Для [5, 3, 4, 11, 2] таблица выглядит так: 0, 5, 5, 9, 16, 16. При k = 4 сравни пропуск дома 3, который даёт best[3] = 9, с тем, чтобы взять из него 11 и прибавить их к best[2] = 5. Выигрывает 16. Ответ — последняя запись. На каждую запись требуется одно сравнение, поэтому время работы составляет O(n), а для таблицы требуется O(n) памяти.

Алгоритм

Создай таблицу best с n + 1 элементами.
Установи best[0] = 0 и best[1] = nums[0].
Для k от 2 до n установи best[k] равным большему из best[k-1] и best[k-2] + nums[k-1].
Верни best[n].

def rob(nums):
    n = len(nums)
    # best[k] is the most you can take from the first k houses
    best = [0] * (n + 1)
    best[1] = nums[0]
    for k in range(2, n + 1):
        # Skip house k-1, or take it on top of the best from the first k-2 houses
        best[k] = max(best[k - 1], best[k - 2] + nums[k - 1])
    return best[n]

Два накапливаемых итога

Идея

Каждая запись таблицы считывает только две записи, стоящие непосредственно перед ней. Когда значение best[k] известно, best[k-2] больше никогда не считывается. Поэтому вместо таблицы храните два числа: twoBack — наилучшую сумму для домов вплоть до дома, отстоящего на два шага назад, и oneBack — наилучшую сумму для домов вплоть до предыдущего дома.

Для дома, в котором хранится x, новое наилучшее значение равно max(oneBack, twoBack + x). Затем сдвиньте значения: twoBack получает старое значение oneBack, а oneBack — новое наилучшее значение. Оба изначально равны 0, что соответствует пустой улице перед первым домом, поэтому для первого дома не нужен отдельный случай: наилучшее значение для него — max(0, 0 + nums[0]).

Для [5, 3, 4, 11, 2] пара принимает значения (0, 0), (0, 5), (5, 5), (5, 9), (9, 16), (16, 16), а в конце oneBack равно 16. Объём работы такой же, O(n), как и при использовании таблицы, а объём памяти сокращается до O(1).

Алгоритм

Установите twoBack и oneBack в 0.
Для каждой суммы x в nums вычислите current = max(oneBack, twoBack + x).
Переместите oneBack в twoBack, затем current в oneBack.
После последнего дома верните oneBack.

def rob(nums):
    # The best totals from the houses up to two back and up to one back
    two_back, one_back = 0, 0
    for amount in nums:
        # Skip this house, or take it on top of the best from two back
        two_back, one_back = one_back, max(one_back, two_back + amount)
    return one_back

Ловушки и крайние случаи

Большинство неправильных ответов связано с упрощённым решением, которое работает на небольших входных данных, или с обновлением двух сумм в неверном порядке.

Если сложить суммы в чётных и нечётных домах и взять большую, можно упустить планы, в которых пропускают два дома подряд. Для [10, 1, 1, 10] обе суммы равны 11, но дома 0 и 3 дают 20.
Если сначала взять самый богатый дом, это не сработает для [3, 4, 3]: ты получишь 4 и не сможешь взять оба дома с 3, которые вместе дают 6.
Если перезаписать oneBack до копирования его значения в twoBack, будет потеряно значение, которое нужно для следующего дома. Сначала вычисли новый максимум, затем сдвинь значения или присвой оба значения одновременно, если язык это позволяет.
Чтение nums[1] или предварительная установка best[1] и best[2] приведёт к ошибке на улице с одним домом. Если начать обе суммы с 0, особый случай не понадобится.
В Lua и R массивы начинаются с 1, поэтому деньги в доме k-1 находятся в nums[k].

Частые вопросы4

Какова рекуррентная формула для задачи «Дом грабителей»?

Наибольшая сумма для первых k домов — это max(best[k-1], best[k-2] + nums[k-1]). Вы либо пропускаете дом k-1 и сохраняете наибольшую сумму для домов до него, либо берёте дом k-1 и прибавляете его стоимость к наибольшей сумме для домов до соседнего с ним. Базовые случаи: 0 домов и nums[0] для одного дома.

Какова временная и пространственная сложность задачи «Грабитель»?

Решение с динамическим программированием рассматривает каждый дом один раз, поэтому работает за время O(n). Полная таблица требует O(n) памяти, а хранение только двух последних итогов снижает расход до O(1). Обычная рекурсия без сохранения ответов выполняет примерно 1.6^n вызовов, что соответствует экспоненциальной сложности.

Почему выбор каждого второго дома не решает задачу «Домушник»?

В лучшем плане иногда пропускаются два дома подряд. В [10, 1, 1, 10] сумма чётных домов и сумма нечётных домов равны 11, а если взять первый и последний дом, получится 20. Динамическое программирование сравнивает варианты пропустить дом и взять его для каждого дома, поэтому находит такие планы.

Как решить задачу «Дом грабителя», если дома расположены по кругу?

На круговой улице первый и последний дома являются соседями, поэтому план может включать не более одного из них. Запусти решение для прямой улицы дважды: один раз без последнего дома, другой — без первого, и верни больший результат. Улица с одним домом — единственный особый случай: ответом будет этот дом.

Python

def rob(nums):
    # Напишите код здесь

Тестовые случаи

Случай 1

Случай 2

Случай 3

Ввод

nums = [5, 3, 4, 11, 2]

Ожидается

House Robber

Функция

Ограничения

Примеры

Подсказки

Решение

Попробуй оба варианта у каждого дома

Таблица снизу вверх

Два накапливаемых итога

Ловушки и крайние случаи

Частые вопросы4

Похожие задачи