Завдання JS про монети «Coin Change»

Умова

Дано монети різного номіналу та деяку суму грошей. Напишіть функцію розрахунку мінімальної кількості монет, якими можна видати цю суму. Якщо це неможливо, то функція повинна повертати -1. Кількість монет кожного номіналу необмежена. - джерело

You are given coins of different denominations and total amount of money amount. Write a function to compute fewest number of coins that you need to make up that amount. Якщо гроші з грошей може бути зроблено будь-якою комбінацією з рейок, повернення -1. Ви можете подумати, що ви маєте 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];
}