Главная страница / Блог / Задачки по программированию / Задачка JS про монеты «Coin Change»

Задачка JS про монеты «Coin Change»

Условие

Даны монеты разного номинала и некоторая сумма денег. Напишите функцию для расчета минимального количества монет, которыми можно выдать эту сумму. Если это невозможно, функция должна возвращать -1. Количество монет каждого номинала неограничено. — источник

You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1. You may assume that you have an infinite number of each kind of coin.

Пример

Input: coins = [1,2,5], amount = 11
Output: 3
Explanation: 11 = 5 + 5 + 1

Решение

Эта проблема решается с помощью динамического программирования, поэтому не следует искать решение «в лоб». Идея решения состоит в том, что мы разбиваем нашу задачу на ряд более простых задач и каждый свой последующий шаг мы делаем на основании предыдущих расчетов.

Расчет для начальных сумм

Для наглядности разберем пример выше. Каким минимальным количеством монет можно выдать 11 центов, имея монеты номинало в 1, 2 и 5 центов? Начнем с малого и на первом этапе мы определим каким минимальным количеством монет можно выдать сумму в один цент. Все просто — одной монетой. А сколько монет необходимо для суммы в два цента? По крайней мере на одну больше, чем для предыдущего случая, т.е. 1 + 1 = 2. Есть нюанс, нас попросили определить минимальное количество монет, а по номиналу монет видно, что два цента можно раздать одной двухцентовой монетой, что меньше того, что мы расчитали.

Расчет для суммы три цента

Заглянем немного в будущее, определим сколько монет необходимо для выдачи трех центов, если мы точно знаем (только что определили на глаз с учетом здравого смысла), что минимальное количество монет для выдачи одного цента — одна, а двух центов — две. Считать будем так: возьмем каждую из монет, отнимем от нужной суммы, посмотрим, сколько будет составлять остаток и на основании ранее расчитаных значений опрелим оптимальное количество монет.

Итак, берем одноцентовую монету и отнимаем от суммы, 3 — 1 = 2. Будем считать, что первую монету (1 цент, который отнимали) мы к выдачи подготовили, а чтоб не считать сколько нужно монет для выдачи остатка, возьмем ответ из ранее расчитаных значений. Смотрим сколько монет мы использовали для выдачи двух центов — одну. Итак, наша одноцентовая и еще одна — дают нам две. Возьмем монету следующего номинала и посмотрим уменьшит ли она итоговое количество монет. Берем двухцентовую монету и отнимаем от суммы 3 — 2 = 1. Смотрим сколько монет нам понадобилось, когда мы раздавали 1 цент и видим — 1. Итого, наша двухцентовая монета и цент дают нам две, что равно предыдущему расчитаному значению. Запомним его, убедимся, что следующая монета (5 центов) не улучшит расчитанный результат (пятицентовой монетой не раздать два цента) и примем его как наиболее оптимальный.

Видно, что увеличивая количество расчетов, мы не усложняем себе задачу, а наоборот упрощаем, так как на каждом шаге мы берем во внимание ранее расчитаные значения.

Алгоритм

Что касается написания алгоритма, то в начале необходимо сделать две вещи — отсортировать массив монет по возрастанию (для оптимизации) и подготовить массив, в котором мы будем хранить все расчитанные значения. Размер такого массива будет составлять необходиммая сумма + 1, так как в расчетах будет фигурировать ноль. Так как мы будем определять наименьшее количество монет для каждой суммы, запишем в каждую ячейку какое-нибудь большое число, чтоб было с чем сравнивать первое вычисленное значение. Первые значения можно указать сразу после инициализации массива.

var coinChange = function(coins, amount) {
    coins.sort((a, b) => a - b);
    const dp = new Array(amount + 1).fill(amount + 1)
    dp[0] = 0;
}

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

for(let i = 0; i <= amount; i++) {
    for(let j = 0; j < coins.length; j++) {
        if (coins[j] <= i) {
           // a place for the coins number definition formula
        } else {
            break;
        }
    }            
}

Теперь самое интересное — формула определения нужного количества монет:

dp[i] = Math.min(dp[i], 1 + dp[i - coins[j]]);

Расчитаное на каждой итерации количество монет мы будем записывать в соответствующую ячейку массива dp, при этом мы смотрим (с помощью метода Math.min), не превышает ли текущее расчетное значение 1 + dp[i — coins[j]] расчитаного ранее dp[i]. Рассмотрим подробнее эту часть:

1 + dp[i - coins[j]]

Тут мы берем монету с текущей итерации coins[j], отнимаем ее от текущей суммы i — coins[j], получаем остаток. Смотрим сколько монет потребовалось для раздачи остатка dp[i — coins[j]]. Итого, монеты с раздачи остатка, плюс одна монета, которую мы отнимали и есть минимальное количество монет, необходимое для выдачи текущей суммы.

Полный код:

/**
 * @param {number[]} coins
 * @param {number} amount
 * @return {number}
 */
var coinChange = function(coins, amount) {
    coins.sort((a, b) => a - b);
    const dp = new Array(amount + 1).fill(amount + 1)
    dp[0] = 0;

    for(let i = 0; i <= amount; i++) {
        for(let j = 0; j < coins.length; j++) {
            if (coins[j] <= i) {
                dp[i] = Math.min(dp[i], 1 + dp[i - coins[j]]);
            } else {
                break;
            }
        }            
    }

    return dp[amount] > amount ? -1 : dp[amount];
}
Russian
Прокрутить вверх