House Robber

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.

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

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

Подсказки

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

Открыто 0 из 3

Решение

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

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

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

Идея

Любой план либо пропускает последний дом, либо грабит его. Если пропустить его, лучший план охватывает первые n-1 домов; если ограбить — к лучшему плану для первых n-2 добавляется nums[n-1]. Итак, 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 миллионов вызовов, а n достигает 10^4.

Алгоритм

Напишите вспомогательную функцию 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, начиная с best[0] = 0 и best[1] = nums[0], затем заполняя её сверху вниз, начиная с k = 2, чтобы оба элемента, которые считываются при вычислении каждого следующего ответа, уже были заполнены.

Для [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]

Две накопительные суммы

Идея

Каждая запись читает только две записи перед ней, поэтому вместо таблицы храни два числа: twoBack и oneBack — наилучшие суммы для домов до дома, находящегося на два шага назад, и до предыдущего дома. Для дома со значением x новая наилучшая сумма равна max(oneBack, twoBack + x); затем сдвинь оба значения. Оба начинаются с 0 — это пустая улица перед первым домом, поэтому для улицы из одного дома не нужен особый случай. Время работы остаётся 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

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

Перезапись oneBack до копирования его в twoBack. Тогда следующий дом использует неправильную сумму. Сначала вычислите новый максимум, а затем выполните сдвиг или присвойте оба значения одновременно.
Чтение nums[1] или предварительная установка best[1] и best[2]. И то и другое не работает на улице с одним домом, например [0].
В Lua и R массивы начинаются с 1, поэтому деньги в доме k-1 находятся в nums[k].

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

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

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

Почему решение «брать каждый второй дом» не подходит для задачи «Грабитель домов»?

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

Как решить задачу «Грабитель домов», когда дома образуют круг?

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

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

Тест #1

Тест #2

Тест #3

Аргумент

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

Ожидаемый вывод

House Robber

Функция

Ограничения

Примеры

Подсказки

Решение

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

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

Две накопительные суммы

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

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

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