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

Вы когда-нибудь писали рекурсивную функцию для вычисления чисел Фибоначчи и ждали, пока она закончится работу? Если да, то вы уже столкнулись с главной проблемой динамического программирования - метода оптимизации алгоритмов, который разбивает сложную задачу на перекрывающиеся подзадачи и сохраняет их результаты для повторного использования. Без этого подхода многие задачи решаются за экспоненциальное время. С ним - за линейное или квадратичное. Разница между секундой и часом выполнения кода.

В этой статье мы не будем гадать о теории. Мы возьмем четыре классические задачи, которые постоянно встречаются на собеседованиях и в реальных проектах, и разберем их шаг за шагом на Python. Это язык, который идеально подходит для прототипирования алгоритмов благодаря своей читаемости и встроенным структурам данных. Вы увидите, как превратить медленный рекурсивный код в быстрый итеративный, используя два ключевых приема: мемоизацию и табличное заполнение (bottom-up).

Суть метода: от рекурсии к таблице

Чтобы понять динамическое программирование, нужно сначала понять, почему обычная рекурсия иногда ломается. Представьте, что вам нужно посчитать количество способов дойти до конца шахматной доски, двигаясь только вправо или вниз. Рекурсивный подход говорит: «чтобы узнать путь в точку (x, y), мне нужно знать пути в точки (x-1, y) и (x, y-1)». Проблема в том, что эти подзадачи часто пересекаются. Вы вычислите одно и то же значение десятки раз заново.

Динамическое программирование решает это двумя способами:

1. Мемоизация (Top-Down): Вы пишете рекурсивную функцию, но храните уже вычисленные ответы в словаре (кэше). Если функция вызывается снова с теми же аргументами, она сразу возвращает сохраненный результат.
2. Табличное заполнение (Bottom-Up): Вы начинаете с самых простых случаев (базового случая) и постепенно строите таблицу ответов, двигаясь к целевому значению. Здесь рекурсия вообще отсутствует.

Оба подхода дают один и тот же результат, но отличаются по использованию памяти и скорости работы. Мемоизация проще для понимания, так как логика остается рекурсивной. Табличное заполнение обычно быстрее, потому что нет накладных расходов на вызовы функций и управление стеком.

Задача 1: Числа Фибоначчи

Это самая известная задача для входа в тему. Нужно найти n-е число последовательности, где каждое следующее равно сумме двух предыдущих. Базовые случаи: F(0)=0, F(1)=1.

Рекурсивное решение без оптимизации имеет сложность O(2^n). Для n=50 оно будет работать вечность. Давайте посмотрим, как исправить это через мемоизацию.

from functools import lru_cache

@lru_cache(maxsize=None)
def fib(n):
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

print(fib(50)) # Выполняется мгновенно

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

def fib_memo(n, memo={}):
    if n in memo:
        return memo[n]
    if n < 2:
        return n
    memo[n] = fib_memo(n - 1, memo) + fib_memo(n - 2, memo)
    return memo[n]

Теперь давайте перейдем к bottom-up подходу. Нам не нужен словарь, нам нужна просто переменная, которая хранит последние два значения.

def fib_iterative(n):
    if n < 2:
        return n
    a, b = 0, 1
    for _ in range(2, n + 1):
        a, b = b, a + b
    return b

Здесь память составляет O(1), а время - O(n). Это самый эффективный вариант для этой конкретной задачи, так как нам нужны только два предыдущих значения, а не вся история.

Задача 2: Лестница (Climbing Stairs)

Представьте лестницу с n ступенями. За один шаг можно подняться на 1 или 2 ступени. Сколько уникальных способов добраться до вершины?

Логика такая же, как у Фибоначчи. Чтобы попасть на ступеньку i, вы могли прийти с i-1 (шаг в 1) или с i-2 (шаг в 2). Поэтому количество способов S(i) = S(i-1) + S(i-2).

Базовые случаи: S(1) = 1 (один способ: шаг в 1), S(2) = 2 (два способа: 1+1 или 2).

Решение итеративным методом выглядит идентично улучшенному варианту Фибоначчи. Единственное отличие - базовые условия. Если n=1, ответ 1. Если n=2, ответ 2. Дальше цикл суммирует предыдущие два значения.

Задача 3: Сумма подмножества (Subset Sum)

Здесь начинается настоящая сила динамического программирования. Дана целочисленная матрица nums и цель target. Нужно определить, существует ли такое подмножество элементов, сумма которых равна target.

Эта задача не сводится к простому сложению последних двух значений. Здесь мы используем булеву таблицу (или множество достижимых сумм). Пусть dp[i][s] означает: «можно ли получить сумму s, используя первые i элементов массива?»

Логика перехода:

• Если мы берем текущий элемент nums[i], то новая сумма = s - nums[i]. Значит, dp[i][s] будет True, если dp[i-1][s - nums[i]] было True.
• Если мы не берем текущий элемент, то dp[i][s] наследует значение dp[i-1][s].

В Python удобно использовать набор (set) достижимых сумм вместо двумерного массива, так как это экономит память и код получается короче.

def can_partition(nums, target):
    possible_sums = {0}
    
    for num in nums:
        # Создаем копию текущего набора, чтобы не изменять его во время итерации
        new_sums = set()
        for s in possible_sums:
            new_sum = s + num
            if new_sum == target:
                return True
            if new_sum < target:
                new_sums.add(new_sum)
        possible_sums.update(new_sums)
        
    return False

Обратите внимание на хитрость: мы создаем new_sums отдельно. Если бы мы добавляли элементы прямо в possible_sums во время цикла, мы могли бы использовать один и тот же элемент дважды, что запрещено условием задачи о подмножестве (обычно каждый элемент можно взять только один раз).

Задача 4: Максимальняя сумма в треугольнике

Дан треугольник из чисел. Нужно найти путь от вершины до основания, проходящий через соседние числа, с максимальной суммой. Это классическая задача, которая часто встречается в системах автоматического тестирования.

Здесь лучше всего работает bottom-up подход. Мы начинаем с последнего ряда и поднимаемся вверх. Для каждого элемента в ряду i мы выбираем максимальное из двух соседей в ряду i+1 и прибавляем к нему свое значение.

def max_triangle_path(triangle):
    if not triangle:
        return 0
    
    # Начинаем с последней строки
    current_row = triangle[-1][:]
    
    # Идем снизу вверх
    for i in range(len(triangle) - 2, -1, -1):
        for j in range(len(triangle[i])):
            left_child = current_row[j]
            right_child = current_row[j + 1]
            current_row[j] = triangle[i][j] + max(left_child, right_child)
    
    return current_row[0]

Этот алгоритм модифицирует список current_row на месте, поэтому пространственная сложность равна O(n), где n - длина последнего ряда. Время - O(N^2), где N - общее количество строк. Это оптимальное решение.

Типичные ошибки новичков

Когда вы начинаете решать такие задачи, есть несколько ловушек, в которые легко попасть:

• Неправильные базовые случаи. В задаче про лестницу многие забывают, что для 1 ступени есть только 1 способ, а для 2 - два. Если задать базу неверно, весь расчет съедет.
• Изменение состояния во время итерации. Как в задаче с подмножеством, если вы меняете основной контейнер данных внутри цикла по нему, вы получаете непредсказуемые результаты. Всегда используйте временную структуру для новых значений.
• Перегрузка памяти. Иногда полная таблица DP не нужна. Если формула зависит только от предыдущего шага (как в Фибоначчи), достаточно хранить две переменные. Это снижает потребление RAM с O(n) до O(1).
• Индексация с нуля vs единицы. В математических записях часто используют 1-based индексацию, а в Python - 0-based. Путаница здесь приводит к ошибкам выхода за границы списка.

Как выбрать подход: Мемоизация или Таблица?

Нет универсального ответа, но есть практические правила:

1. Выбирайте мемоизацию, если рекурсивная логика очевидна и естественна, а размер пространства состояний небольшой (до 10^5 или 10^6). Это быстро писать и легко отлаживать.
2. Выбирайте итерацию (таблицу), если вам важна максимальная скорость и минимальное использование памяти. Особенно если вы знаете, что состояние зависит только от нескольких предыдущих значений.
3. Проверяйте ограничения. Если n может быть 10^9, ни один из этих методов не подойдет напрямую - потребуется матричная возведение или другие математические приемы. DP хорош для n до 10^5-10^6.

В современном Python библиотека functools.lru_cache настолько хороша, что для многих задач мемоизация становится предпочтительным выбором по умолчанию. Она избавляет вас от ручного управления словарем и ошибок с ключами.

Практические советы для собеседований

Если вы готовитесь к техническому интервью, помните следующие моменты:

• Говорите вслух. Объясните, почему задача имеет перекрывающиеся подзадачи. Покажите, что вы понимаете суть, а не просто зубрите код.
• Начните с наивного решения. Напишите рекурсию. Затем спросите себя: «Какие значения я вычисляю повторно?». Это приведет вас к идее кэширования.
• Оцените сложность. Интервьюеры любят слышать анализ Big-O. Скажите: «Время O(n), память O(n), но мы можем снизить память до O(1), если...».
• Обрабатывайте крайние случаи. Пустой список, отрицательные числа, очень большие n. Показывает вашу внимательность.

Динамическое программирование - это не магия. Это дисциплина. Когда вы научитесь видеть повторяющиеся паттерны в подзадачах, решение сложных проблем станет системным процессом, а не творческим актом угадывания.