Метод 1: динамическое программирование
Динамическое программирование — это эффективный подход к решению проблемы минимального сдачи монеты. Он разбивает проблему на более мелкие подзадачи и сохраняет оптимальные решения в таблице.

def min_coin_change(coins, amount):
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0
    for coin in coins:
        for i in range(coin, amount + 1):
            dp[i] = min(dp[i], dp[i - coin] + 1)
    return dp[amount] if dp[amount] != float('inf') else -1

Метод 2: Жадный алгоритм
Жадный алгоритм — это еще один подход, но он не всегда дает оптимальное решение. Он выбирает монету наибольшего номинала, соответствующую оставшейся сумме.

def min_coin_change_greedy(coins, amount):
    coins.sort(reverse=True)
    num_coins = 0
    for coin in coins:
        if coin <= amount:
            num_coins += amount // coin
            amount %= coin
    return num_coins if amount == 0 else -1

Метод 3: рекурсивный подход
Рекурсивный подход можно использовать для решения проблемы минимального сдачи монеты, но он может быть менее эффективным, чем динамическое программирование для больших входных данных.

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