Задача Coin Change: минимальное количество монет — динамическое программирование

Зачем решать задачу Coin Change?

Задача Coin Change — классика собеседований и отличный тренажёр для освоения динамического программирования. Вы научитесь распознавать подзадачи, использовать мемоизацию и писать эффективный код. Разберём пошагово: от грубой силы до оптимизации.

Постановка задачи

Дан массив номиналов монет coins[] и целое число amount — сумма, которую нужно набрать. Каждую монету можно использовать неограниченное количество раз. Верните минимальное количество монет, необходимое для получения суммы. Если это невозможно — верните -1.

Пример: coins = [1, 2, 5], amount = 11 → ответ 3 (5 + 5 + 1).

Грубая сила (Brute Force)

Интуитивно: для каждой суммы перебираем все монеты и рекурсивно ищем решение для остатка. Выбираем минимальное количество монет среди всех вариантов.

def coin_change_brute(coins, amount):
    if amount == 0:
        return 0
    if amount < 0:
        return float('inf')
    min_coins = float('inf')
    for coin in coins:
        res = coin_change_brute(coins, amount - coin)
        if res != float('inf'):
            min_coins = min(min_coins, 1 + res)
    return min_coins

Недостаток: экспоненциальная сложность — одни и те же подзадачи считаются многократно.

Динамическое программирование: мемоизация

Замечаем, что ответ для конкретной суммы не меняется. Сохраним его в массиве dp и будем переиспользовать. Это и есть динамическое программирование сверху вниз (Top-Down DP).

Определение состояния

dp[target] — минимальное количество монет для суммы target.

Переход

Для каждой монеты coin:

dp[target] = 1 + dp[target - coin]

Берём минимум по всем монетам.

Код на Python

def coinChange(coins, amount):
    # Инициализируем dp значением -1 (означает, что не вычислено)
    dp = [-1] * (amount + 1)
    
    def solve(target):
        if target == 0:
            return 0
        if target < 0:
            return float('inf')
        if dp[target] != -1:
            return dp[target]
        min_coins = float('inf')
        for coin in coins:
            res = solve(target - coin)
            if res != float('inf'):
                min_coins = min(min_coins, 1 + res)
        dp[target] = min_coins
        return dp[target]
    
    ans = solve(amount)
    return -1 if ans == float('inf') else ans

Разбор на примере

Пусть coins = [1, 2, 5], amount = 11.

Рекурсивные вызовы:

• Для 11: пробуем монету 1 → solve(10), монету 2 → solve(9), монету 5 → solve(6)
• В итоге находим: 11 = 5 + 5 + 1 → 3 монеты

Таблица dp:

dp[1] = 1
dp[2] = 1
dp[3] = 2
dp[4] = 2
dp[5] = 1
...
dp[11] = 3

Каждое состояние вычисляется ровно один раз.

Анализ сложности

• Время: O(N × amount), где N — количество монет, amount — целевая сумма.
• Память: O(amount) для массива dp и стека рекурсии.

Практический вывод

Освоив Coin Change, вы сможете решать множество похожих задач: Perfect Squares, Minimum Cost Climbing Stairs, Rod Cutting, Unbounded Knapsack. Попробуйте прямо сейчас:

1. Реализуйте итеративный Bottom-Up DP для этой задачи.
2. Решите задачу Perfect Squares на LeetCode.
3. Потренируйтесь объяснять решение на собеседовании за 5 минут.