Coin Change

Q: Какова временная сложность задачи о размене монет?

Решение с динамическим программированием работает за время O(amount × coins) и требует O(amount) памяти: по одной записи в таблице для каждой суммы, и для каждой записи проверяется каждая монета. Обычная рекурсия без мемоизации имеет экспоненциальную сложность по сумме.

Q: Что лучше для задачи о размене монет: подход сверху вниз или снизу вверх?

Оба выполняют одинаковый объём работы O(amount × coins) . Рекурсия сверху вниз может быть вложена на глубину, равную сумме, что приводит к переполнению стека вызовов при 10^4 в нескольких языках. Подход снизу вверх заполняет таблицу циклом, поэтому ограничений по глубине нет, и на собеседовании это более надёжный выбор.

СреднеДинамическое программирование

+10

Тебе дан список coins с различными номиналами монет и целевое значение amount. Ты можешь использовать монету каждого номинала сколько угодно раз. Верни наименьшее количество монет, сумма номиналов которых в точности равна amount, или -1, если набрать эту сумму монетами невозможно. Для суммы 0 требуется 0 монет.

Функция

coinChange(coins: integer-array, amount: integer) → integer

coinsinteger-array: разные номиналы монет, каждый из которых можно использовать любое количество раз
amountinteger: точная сумма к оплате
Возвращаетinteger: минимальное необходимое количество монет или -1, если эту сумму нельзя составить

Ограничения

1 ≤ coins.length ≤ 12
1 ≤ coins[i] ≤ 10⁴
0 ≤ amount ≤ 10⁴
Значения всех монет различаются.

Примеры

Ввод: coins = [2, 5, 10]amount = 27
Вывод: 4
Пояснение: 10 + 10 + 5 + 2 дают 27 четырьмя монетами. Три монеты не подойдут: 27 — нечётное число, поэтому нужна ровно одна монета номиналом 5, а две другие в сумме дают не больше 20, что меньше 22.

Дополнительный вопрос

Можешь посчитать, сколько существует различных комбинаций монет, в сумме дающих amount, вместо того чтобы искать наименьшее количество монет?

Подсказки

Открывайте по одной. Каждая подсказывает чуть больше.

Открыто 0 из 3

Решение

Выбирать самую крупную подходящую монету не получится: монетами номиналом 1, 3 и 4 сумму 6 можно набрать как 4 + 1 + 1, тогда как для 3 + 3 нужны две монеты. Минимальное количество монет для суммы зависит только от минимального количества монет для меньших сумм, поэтому вычисли каждую сумму от 0 до amount один раз.

Попробуйте все комбинации с помощью рекурсии

Верно, но не успевает на самых больших тестах

Идея

Если последняя монета, которой ты платишь, стоит c, то монеты до неё оплачивают сумму remaining - c с наименьшими затратами. Поэтому fewest(remaining) на единицу больше, чем наилучшее значение fewest(remaining - c) среди всех подходящих монет. Этот способ перебирает все последовательности монет, которые не превышают сумму, поэтому он не может пропустить лучший вариант.

Он снова и снова решает задачу для одних и тех же сумм. При монетах 2, 5 и 10 сумма 27 приводит к сумме 15 после оплаты 10 + 2, 2 + 10, 5 + 5 + 2 и других последовательностей, и каждый раз вычисляет 15 с нуля. Число вызовов растёт экспоненциально с увеличением суммы.

Алгоритм

Напиши вспомогательную функцию fewest(remaining), которая возвращает минимальное количество монет для remaining или -1, если подходящего решения нет.
Если remaining равно 0, верни 0.
Для каждой монеты, номинал которой не превышает remaining, вызови вспомогательную функцию для остатка после оплаты этой монетой.
Оставь наименьший результат, отличный от -1, и прибавь к нему единицу за использованную монету.
Верни это количество или -1, если ни одна монета не привела к решению. Ответ — fewest(amount).

def coinChange(coins, amount):
    def fewest(remaining):
        # The fewest coins that add up to remaining, or -1 if no mix does
        if remaining == 0:
            return 0
        best = -1
        for coin in coins:
            if coin <= remaining:
                rest = fewest(remaining - coin)
                if rest != -1 and (best == -1 or rest + 1 < best):
                    best = rest + 1
        return best

    return fewest(amount)

Рекурсия с мемоизацией

Верно, но не успевает на самых больших тестах

Идея

Рекурсия рассматривает только суммы от 0 до amount. Сохраняй каждый ответ в массиве при первом вычислении и возвращай сохранённое значение, когда эта сумма встретится снова. Каждая сумма вычисляется один раз в цикле по монетам: O(amount × coins) операций.

Вызовы по-прежнему вкладываются друг в друга на один уровень за каждую использованную монету. Если номинал монеты равен 1, глубина может достигать 10^4 уровней — больше, чем допускает стек вызовов по умолчанию во многих языках.

Алгоритм

Создай массив memo с ячейками для каждой суммы от 0 до amount, хранящий маркер, который означает, что значение ещё не вычислено.
В fewest(remaining) возвращай 0 для 0, а если в memo[remaining] уже есть ответ, возвращай его.
Иначе попробуй каждую подходящую монету, как в обычной рекурсии, и сохрани наименьший результат плюс один.
Перед возвратом сохрани результат, включая -1, в memo[remaining].
Верни fewest(amount).

def coinChange(coins, amount):
    # memo[r] holds the answer for r once it is worked out; None means not yet
    memo = [None] * (amount + 1)

    def fewest(remaining):
        # The fewest coins that add up to remaining, or -1 if no mix does
        if remaining == 0:
            return 0
        if memo[remaining] is not None:
            return memo[remaining]
        best = -1
        for coin in coins:
            if coin <= remaining:
                rest = fewest(remaining - coin)
                if rest != -1 and (best == -1 or rest + 1 < best):
                    best = rest + 1
        memo[remaining] = best
        return best

    return fewest(amount)

Динамическое программирование снизу вверх по суммам

Идея

Заполняй таблицу fewest, начиная с 0. Когда дойдёшь до суммы t, все меньшие суммы уже обработаны, поэтому fewest[t] на единицу больше наименьшего значения fewest[t-c] среди монет c, которые подходят.

Для сумм, которых нельзя достичь никаким набором монет, используется маркер amount + 1. Каждая монета стоит как минимум 1, поэтому реальный ответ никогда не использует больше amount монет, и маркер проигрывает при любом сравнении. Цикл заменяет рекурсию, поэтому глубина стека вызовов не имеет значения.

Алгоритм

Создай fewest с amount + 1 элементами, присвой каждому значение-маркер amount + 1 и установи fewest[0] равным 0.
Для каждой суммы t от 1 до amount проверь каждую монету c, для которой c ≤ t.
Если fewest[t-c] + 1 меньше, чем fewest[t], сохрани это значение в fewest[t].
После цикла верни -1, если fewest[amount] всё ещё содержит значение-маркер, и fewest[amount] в противном случае.

def coinChange(coins, amount):
    impossible = amount + 1
    fewest = [0] + [impossible] * amount
    for total in range(1, amount + 1):
        for coin in coins:
            if coin <= total and fewest[total - coin] + 1 < fewest[total]:
                fewest[total] = fewest[total - coin] + 1
    return fewest[amount] if fewest[amount] != impossible else -1

Ловушки и крайние случаи

Сначала брать самую крупную монету. Для монет 3 и 5 и суммы 9 это даст 5 и 3, после чего алгоритм упрётся в сумму 1 и вернёт -1, хотя 3 + 3 + 3 работает.
Использовать самое большое целое число в качестве маркера. Прибавление к нему 1 приводит к переполнению и отрицательному числу, которое затем выигрывает при каждом сравнении. Используй amount + 1.
Прибавлять 1 к тупиковой ветви. Если ветвь возвращает -1, прибавление к нему монеты, которую ты использовал, даёт 0, и это значение выигрывает при каждом сравнении. Пропускай результаты -1.
Рекурсивно проходить amount уровней в глубину. При монете номиналом 1 и сумме 10^4 Python остановится на стандартной глубине в 1000 уровней, а в JavaScript, Dart, Ruby и R тоже закончится стек.
Читать fewest[t-c] для монеты номиналом больше t, то есть до начала таблицы.

Частые вопросы3

Почему жадный подход не работает для задачи о размене монет?

Брать самую крупную монету, которая подходит, безопасно только для некоторых систем монет, например для большинства реальных валют. Монетами достоинством 1, 3 и 4 сумму 6 можно набрать тремя монетами вместо двух, а монетами достоинством 3 и 5 вообще нельзя набрать сумму 9. Динамическое программирование сравнивает все варианты, поэтому ни одна система монет не сможет его обмануть.

Какова временная сложность задачи о размене монет?

Решение с динамическим программированием работает за время O(amount × coins) и требует O(amount) памяти: по одной записи в таблице для каждой суммы, и для каждой записи проверяется каждая монета. Обычная рекурсия без мемоизации имеет экспоненциальную сложность по сумме.

Что лучше для задачи о размене монет: подход сверху вниз или снизу вверх?

Оба выполняют одинаковый объём работы O(amount × coins). Рекурсия сверху вниз может быть вложена на глубину, равную сумме, что приводит к переполнению стека вызовов при 10^4 в нескольких языках. Подход снизу вверх заполняет таблицу циклом, поэтому ограничений по глубине нет, и на собеседовании это более надёжный выбор.

def coinChange(coins, amount):
    # Напишите код здесь

Тест #1

Тест #2

Тест #3

Аргументы

coins = [2, 5, 10]
amount = 27

Ожидаемый вывод

Coin Change

Функция

Ограничения

Примеры

Подсказки

Решение

Попробуйте все комбинации с помощью рекурсии

Рекурсия с мемоизацией

Динамическое программирование снизу вверх по суммам

Ловушки и крайние случаи

Частые вопросы3

Похожие задачи