Динамическое программирование: рекурсия, оптимизация и примеры на Python

Динамическое программирование: путь от наивной рекурсии к элегантному решению

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

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

Представьте, что вы грабите дома на улице, но не можете ограбить два соседних. Наивный подход — перебрать все комбинации домов — даёт сложность O(2^n), где n — число домов. Уже при n=50 это невозможно. Но если заметить, что решение для i-го дома зависит только от двух предыдущих, задача сводится к линейному проходу. Это и есть суть динамического программирования: разбить задачу на подзадачи, использовать их результаты и избегать повторных вычислений.

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

ДП применимо, когда выполняются два условия:

• Оптимальная подструктура — решение задачи можно построить из решений подзадач.
• Перекрывающиеся подзадачи — одни и те же подзадачи решаются многократно при наивной рекурсии.

В задаче ограбления домов, пусть dp[i] — максимальная сумма, которую можно получить от первых i домов. Для дома i есть два варианта:

1. Пропустить его — тогда берём dp[i-1].
2. Ограбить его — тогда добавляем его стоимость к dp[i-2] + nums[i].

Рекуррентная формула: dp[i] = max(dp[i-1], dp[i-2] + nums[i]).

Почему это работает? Потому что оптимальное решение для первых i домов либо включает i-й дом, либо нет. Рассмотрев оба случая и выбрав максимум, мы гарантируем оптимальность. Благодаря тому, что dp[i] зависит только от двух предыдущих значений, можно сократить массив до двух переменных и получить O(1) по памяти.

Реализация на Python: от наивной рекурсии к оптимальному коду

Наивная рекурсия (сложность O(2^n))

def rob_bruteforce(nums, i):
    if i < 0:
        return 0
    # либо берём nums[i] и пропускаем i-1, либо пропускаем i
    return max(nums[i] + rob_bruteforce(nums, i-2),
               rob_bruteforce(nums, i-1))

Вызов rob_bruteforce(nums, len(nums)-1) исследует все подмножества — O(2^n) времени и O(n) глубины стека. Уже при n=30 это заметно медленно, а при n=50 — практически невозможно.

Оптимальное решение с ДП (O(n) времени, O(1) памяти)

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(n)? Мы проходим по nums один раз, выполняя константную работу на каждой итерации. Без рекурсии и дополнительных таблиц — только две переменные, хранящие ответы подзадач.

Частая ошибка №1: неправильные базовые случаи

Если инициализировать prev_two и prev_one неправильно (например, оба равны nums[0]), то на первой итерации первый дом будет учтён дважды. Чистый старт с (0, 0) корректно отражает «ещё не рассмотрено ни одного дома».

Частая ошибка №2: использование массива, когда он не нужен

Некоторые выделяют dp = [0] * len(nums) и заполняют его. Хотя это всё ещё O(n) по времени, тратится лишняя память O(n). Трюк с двумя переменными — это настоящая суперсила, как переход от громоздкого рюкзака к лёгкому поясу с инструментами.

Вариации задачи: House Robber II и другие

Задача House Robber (LeetCode 198) — это ровно то, что мы решили. Но есть и усложнённая версия — House Robber II (LeetCode 213), где дома расположены по кругу. Хитрость в том, чтобы запустить тот же алгоритм дважды: один раз исключив первый дом, второй раз — исключив последний, и взять максимум. Основная идея остаётся той же, просто применяем ДП к двум линейным отрезкам.

Эти задачи часто встречаются на собеседованиях в FAANG, потому что проверяют, умеете ли вы находить оптимальную подструктуру и сжимать состояние.

Почему это важно за пределами собеседований

Освоив этот паттерн, вы получите не просто навык для интервью, но и образ мышления для любых задач, где решения строятся на предыдущих и хочется избежать полного перебора. Это пригодится в управлении запасами, распределении ресурсов, разборе текстов с перекрывающимися шаблонами. Как только вы поймёте рекуррентное соотношение «берём или пропускаем», вы начнёте замечать его повсюду, как пасхалки в любимом фильме.

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

Практическое задание для закрепления

Возьмите лист бумаги или откройте любимую IDE и попробуйте решить круговой вариант: дан список стоимости домов по кругу, верните максимальную сумму, не ограбив два соседних дома. Напишите решение в комментариях или опубликуйте в соцсетях с хештегом #DPQuest. Увидим, как вы применяете полученную силу!

Помните: каждый великий герой начинал с одного озарения. Пусть это будет ваше. Удачного кодинга! 🚀