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

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

Состояние

Состояние хранит всю информацию о префиксе или позиции, которая влияет на будущее, и ничего лишнего. Например, dp[i] может означать число способов добраться до клетки i, а dp[i][w] — лучший результат для первых i предметов и ограничения w.

Переход

Формула перечисляет последний шаг, которым можно прийти в состояние. Для числа путей складывают независимые варианты, для оптимума выбирают минимум или максимум. Каждый допустимый объект должен соответствовать ровно одному последнему шагу, иначе появится пропуск или двойной счёт.

База и порядок

Начальные состояния задают задачи минимального размера. Вычислять нужно так, чтобы все зависимости были готовы: слева направо, по слоям, в топологическом порядке или рекурсивно с мемоизацией. Циклическая зависимость сигнализирует о неверной модели либо о необходимости другого метода.

Память и восстановление

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

Чек-лист доказательства

Дайте словесное определение dp, докажите полноту и однозначность последнего шага, объясните базу и порядок. Проверьте нулевой размер и недостижимое состояние. Только после этого оценивайте число состояний и стоимость перехода: их произведение обычно задаёт время алгоритма.

Состояние должно содержать всё нужное и ничего лишнего

В задаче о минимальном числе монет dp[amount] хранит оптимальное число монет для точной суммы amount. Переход перебирает последнюю монету. Бесконечность отличает недостижимую сумму от суммы, для которой найдено решение; массив parent позволяет восстановить состав.

def min_coins(total: int, coins: list[int]) -> list[int] | None:
    if total < 0 or any(coin <= 0 for coin in coins):
        raise ValueError("non-negative total and positive coins required")
    if total == 0:
        return []
    dp = [0] + [float("inf")] * total
    parent = [-1] * (total + 1)
    for amount in range(1, total + 1):
        for coin in coins:
            if coin <= amount and dp[amount - coin] + 1 < dp[amount]:
                dp[amount] = dp[amount - coin] + 1
                parent[amount] = coin
    if parent[total] == -1:
        return None
    result: list[int] = []
    while total:
        result.append(parent[total]); total -= parent[total]
    return result

Жадный выбор самой крупной монеты работает не для каждого набора номиналов; динамика не делает такого предположения.

Практика: контрпример жадному подходу

Для монет [1, 3, 4] и суммы 6 сравните жадный ответ с динамическим. Выпишите таблицу dp и обоснуйте каждый переход через последнюю монету. Проверьте набор [4, 6] для недостижимых сумм и нулевую сумму. Затем измените задачу: посчитайте количество различных последовательностей монет. Объясните, почему порядок циклов влияет на то, считаются ли перестановки одним или разными способами.