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

Почему динамическое программирование даётся тяжелее других тем

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

Главная ошибка: запоминание решений вместо паттернов

Самая распространённая ошибка при подготовке к собеседованиям — решать задачи без анализа паттернов. Можно прорешать 300 задач на LeetCode и всё равно растеряться на новой, потому что вы запоминали решения, а не строили ментальную модель. Для DP это критично. Запомнив решение задачи о размене монет, вы не справитесь с её вариантом с другими ограничениями. Запомнив рюкзак — не решите задачу с двумя измерениями состояния. Нужно уметь смотреть на незнакомую задачу и с нуля выводить, подходит ли DP, каким должно быть состояние и рекуррентное соотношение. Этот навык тренируется через осознанную практику распознавания и конструирования, а не через заучивание ответов.

Как распознать DP-задачу с нуля

Два ключевых свойства, которые указывают на DP:

• Оптимальная подструктура (optimal substructure): оптимальное решение всей задачи можно построить из оптимальных решений подзадач.
• Перекрывающиеся подзадачи (overlapping subproblems): одни и те же подзадачи возникают многократно при рекурсивном решении. DP позволяет вычислить каждую подзадачу один раз и сохранить результат.

Пятишаговая проверка:

1. Цель — оптимизировать (минимизировать/максимизировать) или подсчитать количество способов?
2. Можно ли разбить задачу на более мелкие подзадачи того же типа?
3. Перекрываются ли эти подзадачи (одни и те же входные данные появляются в разных ветках рекурсии)?
4. Можно ли определить чёткое состояние, которое описывает всю информацию для подзадачи?
5. Можно ли выразить рекуррентное соотношение — правило, как решение большей задачи строится из решений меньших?

Если ответ «да» на все пять — перед вами DP-задача. Если на вопросы 4 или 5 ответ неясен — кодить рано.

Правильный порядок изучения динамического программирования

Многие начинают с восходящего DP (tabulation), потому что в решениях он выглядит чисто. Это ошибка. Нисходящий подход (top-down) интуитивнее: вы пишете рекурсивное решение, добавляете кеш — и получаете мемоизированный DP. Правильный порядок:

1. Освойте рекурсию. Без уверенной рекурсии DP покажется невозможным.
2. Изучите нисходящий DP (мемоизация). Добавьте кеш, проверяйте его перед вычислением, сохраняйте результат после.
3. Переходите к восходящему DP (табуляция). Определите базовые случаи, порядок вычислений и заполните таблицу итеративно.

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

Пять ключевых паттернов DP

Линейное DP

Состояние зависит от одного индекса, движущегося по массиву или строке. Классика — наибольшая возрастающая подпоследовательность.

def length_of_lis(nums):
    if not nums:
        return 0
    dp = [1] * len(nums)  # dp[i] — длина НВП, оканчивающейся на i
    for i in range(len(nums)):
        for j in range(i):
            if nums[j] < nums[i]:
                dp[i] = max(dp[i], dp[j] + 1)
    return max(dp)

Рюкзак (Knapsack)

Состояние включает вместимость и набор предметов. Решаете, включать или исключать каждый предмет. Пример: 0-1 рюкзак, неограниченный рюкзак, задачи разбиения.

def knapsack_01(weights, values, capacity):
    n = len(weights)
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        for w in range(capacity + 1):
            if weights[i-1] <= w:
                dp[i][w] = max(dp[i-1][w], dp[i-1][w - weights[i-1]] + values[i-1])
            else:
                dp[i][w] = dp[i-1][w]
    return dp[n][capacity]

Наибольшая общая подпоследовательность (LCS)

Состояние — два индекса, движущихся по двум последовательностям. Используется для расстояния редактирования, наибольшей общей подстроки.

def longest_common_subsequence(text1, text2):
    m, n = len(text1), len(text2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if text1[i-1] == text2[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
    return dp[m][n]

DP на сетке (Grid DP)

Состояние — позиция в двумерной сетке, движение под ограничениями. Примеры: уникальные пути, минимальная сумма пути.

def unique_paths(m, n):
    dp = [[1] * n for _ in range(m)]
    for i in range(1, m):
        for j in range(1, n):
            dp[i][j] = dp[i-1][j] + dp[i][j-1]
    return dp[m-1][n-1]

Интервальное DP (Interval DP)

Состояние — диапазон индексов, решения о разделении или слиянии. Примеры: умножение матричной цепочки, лопание шариков.

def matrix_chain_order(p):
    n = len(p) - 1
    dp = [[0] * n for _ in range(n)]
    for length in range(2, n + 1):  # длина цепочки
        for i in range(n - length + 1):
            j = i + length - 1
            dp[i][j] = float('inf')
            for k in range(i, j):
                cost = dp[i][k] + dp[k+1][j] + p[i] * p[k+1] * p[j+1]
                dp[i][j] = min(dp[i][j], cost)
    return dp[0][n-1]

Когда встречаете новую DP-задачу, первый вопрос не «какое решение?», а «на какой из этих паттернов похожа задача и как состояние и рекуррентное соотношение отображаются на этот паттерн?»

Как практиковать DP, чтобы реально прогрессировать

1. Тренируйте распознавание паттернов до кода. Первые пять минут только анализируйте: есть ли оптимальная подструктура? Перекрывающиеся подзадачи? Каким должно быть состояние? Не пишите код, пока не ответите на эти вопросы.
2. Решайте top-down, затем конвертируйте в bottom-up. Это строит интуицию, почему таблица устроена именно так.
3. Группируйте практику по паттернам, затем перемешивайте. Сначала решите несколько задач одного семейства, потом чередуйте с другими, чтобы тренировать распознавание.
4. Отслеживайте слабые подтипы. DP — не единый навык. Рюкзак, интервальное DP и DP на сетке имеют разные признаки. Если слабы именно в интервальном DP, практика рюкзака не закроет пробел.
5. Восстанавливайте решение по памяти на следующий день. Закройте ноутбук после решения. На следующий день попробуйте воссоздать решение с нуля, используя только определение состояния и рекуррентное соотношение. Это лучший тест на понимание.

Главные выводы

Динамическое программирование сложно из-за распознавания и определения состояния, а не из-за реализации. Запоминание решений пропускает самую трудную часть и оставляет вас беспомощным перед вариантами. Два свойства, подтверждающие DP: оптимальная подструктура и перекрывающиеся подзадачи. Изучайте рекурсию, затем нисходящий DP, затем восходящий. Фокусируйтесь на пяти паттернах: линейное DP, рюкзак, LCS, DP на сетке, интервальное DP. Тренируйте распознавание паттернов как отдельный навык. Отслеживайте успеваемость по подтипам DP, а не в целом.

Часто задаваемые вопросы

Почему динамическое программирование так сложно для большинства разработчиков?

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

Как понять, что задача требует DP?

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

Что учить сначала: top-down или bottom-up DP?

Top-down (мемоизацию). Он интуитивнее, так как следует естественной рекурсивной структуре. Пишете рекурсивное решение, добавляете кеш — готово. Bottom-up (табуляцию) учите вторым, как конвертацию top-down, чтобы понимать, почему таблица устроена так, а не просто заполнять её по шаблону.

Какие паттерны DP самые важные для собеседований?

Пять паттернов покрывают большинство задач: линейное DP (наибольшая возрастающая подпоследовательность, house robber), рюкзак (0-1 рюкзак, partition equal subset sum), LCS (расстояние редактирования, distinct subsequences), DP на сетке (уникальные пути, минимальная сумма пути) и интервальное DP (лопание шариков, умножение матричной цепочки). Умение распознавать эти паттерны и отображать на них новые задачи ценнее запоминания любого отдельного решения.