322. Coin Change

Задача

Даны монеты разных номиналов coins и сумма amount. Верните минимальное число монет для набора суммы (или -1).

Примеры

Пример 1

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

Пояснение

11 = 5 + 5 + 1.

Пример 2

Input: coins = [2], amount = 3
Output: -1

Пример 3

Input: coins = [1], amount = 0
Output: 0

Решение

Решение

/**
 * Логика:
 * - Строим решение от базового случая (сумма 0) к целевой сумме
 * - Для каждой суммы пробуем все монеты и выбираем минимум
 * - Используем результаты меньших сумм для построения больших
 * 
 * Временная сложность: O(amount × coins.length)
 * Пространственная сложность: O(amount)
 * 
 * Плюсы: Оптимально, нет риска переполнения стека, понятный порядок вычислений
 * Минусы: Вычисляет все подзадачи, даже если некоторые не нужны
 */
var coinChange_BottomUp = function (coins, amount) {
    // dp[i] = минимальное количество монет для суммы i
    const dp = new Array(amount + 1).fill(Infinity);
    dp[0] = 0; // базовый случай: для 0 нужно 0 монет
 
    // Перебираем все суммы от 1 до amount
    for (let i = 1; i <= amount; i++) {
        // Для каждой суммы пробуем все монеты
        for (const coin of coins) {
            if (coin <= i) {
                // Берём решение для остатка и добавляем текущую монету
                dp[i] = Math.min(dp[i], dp[i - coin] + 1);
            }
        }
    }
 
    return isFinite(dp[amount]) ? dp[amount] : -1;
};

Решение 2 (Dynamic Programming (Top-Down + Memo))

/**
 * Логика:
 * - Начинаем с целевой суммы и рекурсивно разбиваем на подзадачи
 * - Пробуем вычесть каждую монету и рекурсивно решить для остатка
 * - Кешируем результаты, чтобы не пересчитывать одинаковые подзадачи
 * 
 * Временная сложность: O(amount × coins.length)
 * Пространственная сложность: O(amount) для memo + O(amount) для стека рекурсии
 * 
 * Плюсы: Интуитивный, вычисляет только нужные подзадачи
 * Минусы: Риск переполнения стека при больших amount, больше памяти
 */
var coinChange_TopDown = function (coins, amount) {
    const memo = new Map();
 
    function dp(remaining) {
        // Базовые случаи
        if (remaining === 0) return 0;           // сумма набрана
        if (remaining < 0) return Infinity;      // перебор
 
        // Проверяем кеш
        if (memo.has(remaining)) {
            return memo.get(remaining);
        }
 
        // Пробуем каждую монету
        let minCoins = Infinity;
        for (const coin of coins) {
            const result = dp(remaining - coin) + 1;
            minCoins = Math.min(minCoins, result);
        }
 
        // Сохраняем в кеш
        memo.set(remaining, minCoins);
        return minCoins;
    }
 
    const result = dp(amount);
    return isFinite(result) ? result : -1;
};

Решение 3 (BFS)

/**
 * Логика:
 * - Рассматриваем задачу как граф: вершины = суммы, рёбра = монеты
 * - Ищем кратчайший путь от 0 до amount
 * - Обходим по уровням: уровень = количество монет
 * - Первый раз достигли amount = минимальное количество монет
 * 
 * Временная сложность: O(amount × coins.length)
 * Пространственная сложность: O(amount) для очереди и посещённых
 * 
 * Плюсы: Естественный поиск минимума (первое найденное = оптимальное)
 * Минусы: Больше памяти для очереди, сложнее реализация
 */
var coinChange_BFS = function (coins, amount) {
    if (amount === 0) return 0;
 
    const queue = [0];              // начинаем с суммы 0
    const visited = new Set([0]);   // чтобы не обрабатывать дважды
    let level = 0;                  // количество монет
 
    while (queue.length > 0) {
        const size = queue.length;
        level++; // добавляем ещё одну монету
 
        // Обрабатываем все суммы текущего уровня
        for (let i = 0; i < size; i++) {
            const currentSum = queue.shift();
 
            // Пробуем добавить каждую монету
            for (const coin of coins) {
                const newSum = currentSum + coin;
 
                // Нашли ответ
                if (newSum === amount) {
                    return level;
                }
 
                // Добавляем в очередь, если не превысили и не посещали
                if (newSum < amount && !visited.has(newSum)) {
                    queue.push(newSum);
                    visited.add(newSum);
                }
            }
        }
    }
 
    return -1; // достичь amount невозможно
};