Размен монет

Размен монет — Решение

Описание задачи

Размен монет (Coin Change) — это классическая задача динамического программирования. Требуется найти минимальное количество монет заданных номиналов, которые суммируются в целевую сумму. Это практическая задача, используемая в системах обработки платежей и автоматах.

Подход 1: Динамическое программирование (Bottom-Up)

Это оптимальный способ решения задачи. Мы создаём массив dp, где dp[i] — минимальное количество монет для суммы i.

def coin_change(coins: list[int], amount: int) -> int:
    # Инициализируем массив с "бесконечностью"
    dp = [float("inf")] * (amount + 1)
    dp[0] = 0  # 0 монет нужно для суммы 0
    
    # Для каждой суммы от 1 до target
    for i in range(1, amount + 1):
        # Пробуем каждую монету
        for coin in coins:
            if coin <= i:
                # Обновляем минимум
                dp[i] = min(dp[i], dp[i - coin] + 1)
    
    # Если dp[amount] остался "бесконечностью" — размен невозможен
    return dp[amount] if dp[amount] != float("inf") else -1

# Примеры
print(coin_change([1, 2, 5], 11))  # 3
print(coin_change([2], 3))           # -1
print(coin_change([10], 5))          # -1
print(coin_change([1, 3, 4], 6))     # 2 (4 + 1 + 1)

Как это работает:

1. Создаём массив dp размером amount + 1, заполненный "бесконечностью"
2. Устанавливаем dp[0] = 0 (для суммы 0 нужно 0 монет)
3. Для каждой суммы i от 1 до amount:
   • Берём каждую монету coin
   • Если монета ≤ текущей суммы, проверяем: dp[i - coin] + 1
   • Это означает: "добавим ещё одну монету к оптимальному решению для суммы i - coin"
   • Запоминаем минимум
4. Если dp[amount] так и остался "бесконечностью", размен невозможен

Сложность:

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

Подход 2: Рекурсия с Memoization (Top-Down)

Вариант с запоминанием результатов (мемоизация) часто более интуитивен:

def coin_change_memo(coins: list[int], amount: int) -> int:
    memo = {}
    
    def dp(remaining: int) -> int:
        # Базовые случаи
        if remaining == 0:
            return 0
        if remaining < 0:
            return -1
        
        # Если уже вычисляли — возвращаем
        if remaining in memo:
            return memo[remaining]
        
        # Инициализируем минимум "бесконечностью"
        min_coins = float("inf")
        
        # Пробуем каждую монету
        for coin in coins:
            result = dp(remaining - coin)
            if result >= 0:  # Если размен возможен
                min_coins = min(min_coins, result + 1)
        
        # Сохраняем результат
        memo[remaining] = -1 if min_coins == float("inf") else min_coins
        return memo[remaining]
    
    return dp(amount)

print(coin_change_memo([1, 2, 5], 11))  # 3

Подход 3: BFS (Поиск в ширину)

Интересный альтернативный подход — трактовать задачу как поиск кратчайшего пути:

from collections import deque

def coin_change_bfs(coins: list[int], amount: int) -> int:
    if amount == 0:
        return 0
    
    visited = {0}
    queue = deque([(0, 0)])  # (текущая_сумма, количество_монет)
    
    while queue:
        current_sum, count = queue.popleft()
        
        for coin in coins:
            new_sum = current_sum + coin
            
            if new_sum == amount:
                return count + 1
            
            if new_sum < amount and new_sum not in visited:
                visited.add(new_sum)
                queue.append((new_sum, count + 1))
    
    return -1

print(coin_change_bfs([1, 2, 5], 11))  # 3

Сравнение подходов

Оптимизация: Coin Change 2 (количество способов)

Если нужно найти количество способов размена (не минимум монет), используем DP:

def change(amount: int, coins: list[int]) -> int:
    dp = [0] * (amount + 1)
    dp[0] = 1  # Один способ составить 0 — не брать монет
    
    for coin in coins:
        for i in range(coin, amount + 1):
            dp[i] += dp[i - coin]
    
    return dp[amount]

print(change(5, [1, 2, 5]))  # 4 способа: [5], [2,2,1], [2,1,1,1], [1,1,1,1,1]

Заключение

Задача о размене монет демонстрирует силу динамического программирования. Ключевая идея: разбиваем задачу на подзадачи, решаем их по порядку и запоминаем результаты. Это фундаментальный паттерн в алгоритмике.