Задача «Размена монет» — это классическая алгоритмическая задача, которая включает в себя поиск минимального количества монет, необходимых для внесения определенного количества сдачи. В этой статье блога мы рассмотрим несколько методов решения этой проблемы, а также приведем примеры кода, чтобы обеспечить полное понимание различных подходов. Давайте погрузимся!

Метод 1: перебор (рекурсивный)
Метод перебора включает в себя исчерпывающую проверку всех возможных комбинаций монет, чтобы найти минимально необходимое количество монет. Хотя это неэффективно, оно служит хорошей отправной точкой для понимания проблемы.

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

Метод 2: динамическое программирование (сверху вниз)
Динамическое программирование — это более эффективный подход, позволяющий избежать избыточных вычислений за счет сохранения ранее вычисленных результатов. Этот нисходящий подход, также известный как мемоизация, использует кеш для хранения промежуточных значений.

def coin_change(coins, amount, cache={}):
    if amount in cache:
        return cache[amount]
    if amount == 0:
        return 0
    if amount < 0:
        return float('inf')
    min_coins = float('inf')
    for coin in coins:
        min_coins = min(min_coins, 1 + coin_change(coins, amount - coin, cache))
    cache[amount] = min_coins
    return min_coins

Метод 3: динамическое программирование (снизу вверх).
При восходящем подходе к динамическому программированию решение строится итеративно, начиная с базового случая и постепенно вычисляя оптимальное решение для более крупных подзадач.

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

Метод 4: Жадный алгоритм
При использовании жадного алгоритма на каждом этапе выбирается монета наибольшего номинала. Однако это не всегда может дать оптимальное решение для всех монетных систем.

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