Динамическое программирование на Python: базовый паттерн

Почему динамическое программирование — ваш ключ к сложным задачам

Вы когда-нибудь сталкивались с задачей, где нужно перебрать все варианты, но их экспоненциально много? Например, ограбить дома так, чтобы не взять два соседних, и получить максимум денег. Первая мысль — проверить все подмножества, но при 20 домах это уже 2^20 вариантов — слишком медленно. Динамическое программирование (ДП) позволяет решать такие задачи за линейное время, запоминая промежуточные результаты. В этой статье вы освоите базовый паттерн ДП на Python и сможете применять его к десяткам похожих задач.

Основная идея: запоминайте, чтобы не пересчитывать

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

Для задачи ограбления домов состояние — это максимальная сумма, которую можно получить, рассматривая дома до i-го включительно. Переход: либо пропускаем i-й дом (тогда берём лучший результат для i-1), либо грабим его (тогда прибавляем его стоимость к лучшему результату для i-2, потому что i-1 трогать нельзя). Формула:

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

Почему это работает? Любое оптимальное решение для первых i домов либо включает i-й дом, либо нет. Если нет — это оптимальное решение для i-1 домов. Если да — i-1 не берём, значит, прибавляем nums[i] к оптимальному решению для i-2. Других вариантов нет, поэтому рекуррентность полная. Заполняя массив слева направо, мы используем только предыдущие значения, получая O(n) времени и O(1) дополнительной памяти, если хранить только два последних результата.

Реализация: от перебора к ДП

Наивный перебор (неэффективно)

from itertools import combinations

def rob_brute(nums):
    """Перебор всех подмножеств: экспоненциальная сложность"""
    n = len(nums)
    best = 0
    for r in range(n + 1):
        for combo in combinations(range(n), r):
            # Проверяем, что нет соседних домов
            if all(abs(combo[i] - combo[i + 1]) > 1 for i in range(len(combo) - 1)):
                best = max(best, sum(nums[i] for i in combo))
    return best

Уже для 20 домов этот код работает мучительно долго — как ожидание босса в игре.

Решение через ДП (оптимально)

def rob(nums):
    """
    Возвращает максимальную сумму, которую можно ограбить,
    не трогая соседние дома.
    """
    prev_two, prev_one = 0, 0  # dp[i-2], dp[i-1]
    for money in nums:
        current = max(prev_one, prev_two + money)
        prev_two, prev_one = prev_one, current
    return prev_one

Почему это мощно:

• Храним только две переменные — память O(1).
• Каждый дом обрабатывается один раз — время O(n).
• Нет рекурсии и больших таблиц.

Частая ошибка №1: забываем базовый случай

Если начать с prev_two = nums[0] и prev_one = max(nums[0], nums[1]), то на пустом списке или списке из одного элемента будет ошибка. Инициализация (0, 0) безопасна для любой длины — цикл сам построит верный ответ.

Частая ошибка №2: неправильные индексы

Некоторые пишут dp[i] = max(dp[i-1], dp[i-2]) + nums[i] — это прибавляет стоимость дома к обоим вариантам, что приводит к двойному учёту при пропуске. Помните: деньги добавляются только в ветку «берём».

Ещё один пример: максимальная сумма подмассива (алгоритм Кадане)

Тот же принцип «храним лучшее на текущий момент» решает классическую задачу о максимальной сумме подмассива за O(n):

def max_subarray(nums):
    best = cur = nums[0]
    for x in nums[1:]:
        cur = max(x, cur + x)  # либо начинаем новый подмассив, либо расширяем
        best = max(best, cur)
    return best

Почему это работает? На каждой позиции лучший подмассив, заканчивающийся здесь, — это либо сам элемент (начало нового), либо предыдущий лучший, расширенный этим элементом. Отслеживая глобальный максимум, получаем ответ.

Как применять этот паттерн в других задачах

Освоив этот паттерн, вы сможете решить множество задач на собеседованиях: House Robber, Maximum Subarray, Climbing Stairs, минимальная стоимость покраски домов и даже более сложные варианты, например, «ограбление домов по кругу» (запустите алгоритм дважды).

Главное — сдвиг мышления: вместо «перебрать всё» вы спрашиваете «какую минимальную информацию нужно запомнить, чтобы строить решение дальше?». Этот сдвиг превращает мучительный перебор в элегантный алгоритм. Вы начнёте замечать перекрывающиеся подзадачи повсюду: редактирование строк, пути в сетке, игровые стратегии.

Практический вывод: ваше следующее действие

Выберите задачу, которая вам раньше не давалась, например, «минимальная сумма пути в треугольнике» или «максимальная прибыль с периодом охлаждения». Запишите состояние, переход и реализуйте решение с O(n) времени и O(1) памяти. Поделитесь кодом в комментариях — интересно увидеть, как разные люди применяют один и тот же приём.

Успешного кодинга, и пусть ваши приключения с ДП будут такими же эпичными, как восхождение героя к легенде!