Ограбление домов: разбор динамического программирования на Python

Помните своё первое знакомство с задачей House Robber на LeetCode? Вы смотрите на условие: дан массив неотрицательных целых чисел — сумма денег в каждом доме. Нужно вернуть максимальную сумму, которую можно украсть, не ограбив два соседних дома (иначе сработает сигнализация). Первая мысль: написать рекурсию, перебирающую все комбинации. И через минуту вы видите, как стек вызовов растёт экспоненциально — для массива длиной 30 это уже катастрофа.

Но есть способ reuse уже проделанной работы — динамическое программирование (DP). В этой статье мы на примере House Robber разберём, как превратить экспоненциальный перебор в линейный проход с O(1) памяти. Вы поймёте не просто формулу, а почему она работает, и сможете применять этот паттерн к другим задачам.

Оптимальная подструктура и перекрывающиеся подзадачи

Задача House Robber обладает свойством оптимальной подструктуры: оптимальное решение для первых i домов можно построить из решений для i-1 и i-2. А именно:

• Пропустить дом i → берём лучшее для i-1.
• Ограбить дом i → прибавляем его значение к лучшему для i-2 (так как i-1 трогать нельзя).

Формально, пусть dp[i] — максимальная сумма для домов с 0 по i. Тогда:

dp[i] = max(dp[i-1], dp[i-2] + nums[i])

Базовые случаи: dp[0] = nums[0], dp[1] = max(nums[0], nums[1]).

Обратите внимание: для вычисления dp[i] нужны только два предыдущих значения. Это значит, что мы можем хранить не весь массив DP, а всего две переменные — пространственная сложность O(1).

От рекурсии к линейному DP: код на Python

Что НЕ надо делать: экспоненциальная рекурсия

def rob_rec(nums, i):
    if i < 0:
        return 0
    # ограбить этот дом или пропустить
    return max(rob_rec(nums, i-1), rob_rec(nums, i-2) + nums[i])

def rob(nums):
    return rob_rec(nums, len(nums)-1)

Этот код работает, но для массива из 30 элементов будет выполняться вечность. Не делайте так на собеседовании.

Правильное решение: DP с двумя переменными

def rob(nums):
    if not nums:
        return 0
    if len(nums) == 1:
        return nums[0]
    prev2 = nums[0]          # dp[i-2]
    prev1 = max(nums[0], nums[1])  # dp[i-1]
    for i in range(2, len(nums)):
        curr = max(prev1, prev2 + nums[i])
        prev2, prev1 = prev1, curr  # сдвигаем окно
    return prev1

Как это работает: на каждом шаге мы вычисляем текущее значение, используя только два предыдущих. Цикл движется как конвейер — никакого возврата назад, никаких повторных вычислений. Время O(n), память O(1).

Частые ошибки:

• Забыть обработать пустой массив — вернуть 0.
• Использовать массив для DP, когда достаточно двух переменных.

Усложнение: House Robber II (круговая улица)

Теперь дома расположены по кругу — нельзя ограбить первый и последний одновременно. Решение: запустить линейный DP дважды:

• Исключить первый дом (рассмотреть nums[1:]).
• Исключить последний дом (рассмотреть nums[:-1]).
• Взять максимум из двух результатов.

def rob(nums):
    if len(nums) == 1:
        return nums[0]
    return max(rob_linear(nums[1:]), rob_linear(nums[:-1]))

def rob_linear(arr):
    prev2 = prev1 = 0
    for val in arr:
        curr = max(prev1, prev2 + val)
        prev2, prev1 = prev1, curr
    return prev1

Всё ещё O(n) времени и O(1) памяти.

Почему этот паттерн важен?

Освоив House Robber, вы научитесь видеть оптимальную подструктуру и перекрывающиеся подзадачи в других задачах: Delete and Earn, Maximum Sum of Non-Adjacent Elements, Stock Buy-Sell with Cooldown и многих других. Принцип «хранить только два последних состояния» превращает DP из тяжёлой теории в лёгкий инструмент, который можно объяснить за чашкой кофе.

Ваша очередь

Возьмите лист бумаги (или откройте IDE) и попробуйте решить Maximum Subarray Sum (алгоритм Кадане) тем же способом: найдите рекуррентное соотношение, храните только необходимое, итерируйте. Напишите своё решение в комментариях — обсудим!

Удачи в кодинге, и пусть DP будет с вами! 🚀