Задача о размене монет: подробный разбор решения

Почему эта задача важна?

Задача о размене монет — это классическая проблема динамического программирования, которая позволяет оценить:

• 🧠 Понимание принципов динамического программирования
• ⚡ Навыки решения задач с оптимальной подструктурой
• 🎯 Умение анализировать различные алгоритмические подходы
• 🔍 Способность выявлять перекрывающиеся подзадачи
• 💵 Практические навыки для финансовых и экономических приложений

Постановка задачи

Основная формулировка (минимальное количество монет):

Дан набор номиналов монет и сумма денег. Найти минимальное количество монет, необходимое для размена данной суммы. Если разменять невозможно, вернуть -1.

Вариация задачи (количество способов размена):

Дан набор номиналов монет и сумма денег. Найти количество различных способов разменять данную сумму с использованием имеющихся монет.

Примеры:

// Минимальное количество монет (Вариант 1)
// Первый пример ✅
Input: 
coins = [1, 2, 5]
amount = 11

Output: 3
Объяснение: 11 = 5 + 5 + 1 (всего 3 монеты)

// Второй пример ✅
Input:
coins = [2]
amount = 3

Output: -1
Объяснение: Нельзя разменять 3 монетами номиналом 2

// Количество способов размена (Вариант 2)
// Пример ✅
Input:
coins = [1, 2, 5]
amount = 5

Output: 4
Объяснение: Есть 4 способа размена:
5 = 5
5 = 2 + 2 + 1
5 = 2 + 1 + 1 + 1
5 = 1 + 1 + 1 + 1 + 1

Пройди собеседование в топ-компанию

Платформа для подготовки

Решай алгоритмические задачи как профи

✓ Популярные алгоритмы✓ Разбор решений✓ AI помощь

Начать сейчас→

Варианты задачи о размене монет

Задача 1: Минимальное количество монет

Найти минимальное количество монет, необходимое для размена заданной суммы.

Задача 2: Количество способов размена

Найти количество различных способов разменять заданную сумму.

Задача 3: Разменять с ограниченным запасом монет

Найти оптимальный способ размена, когда количество монет каждого номинала ограничено.

Давайте рассмотрим решения для каждого варианта задачи.

Минимальное количество монет

Решение 1: Рекурсия с возвратом (greedy + backtracking) 🔍

function coinChangeRecursive(coins, amount) {
  // Сортируем монеты по убыванию для жадного подхода
  coins.sort((a, b) => b - a);
  
  let minCoins = Infinity;
  
  function backtrack(index, remaining, count) {
    // Базовый случай: мы разменяли точную сумму
    if (remaining === 0) {
      minCoins = Math.min(minCoins, count);
      return;
    }
    
    // Если превысили сумму или перебрали все монеты
    if (remaining < 0 || index >= coins.length) {
      return;
    }
    
    // Если текущее количество монет уже больше найденного минимума,
    // дальнейший поиск бессмысленен
    if (count + Math.ceil(remaining / coins[index]) >= minCoins) {
      return;
    }
    
    // Жадный подход: сначала пробуем взять максимальное количество текущей монеты
    const maxCount = Math.floor(remaining / coins[index]);
    
    // Перебираем все варианты количества текущей монеты (от максимального до 0)
    for (let i = maxCount; i >= 0; i--) {
      backtrack(
        index + 1,
        remaining - coins[index] * i,
        count + i
      );
    }
  }
  
  backtrack(0, amount, 0);
  
  return minCoins === Infinity ? -1 : minCoins;
}

Анализ решения:

✅ Применяет жадную эвристику для ускорения перебора

✅ Может находить точное решение

❌ Экспоненциальная временная сложность в худшем случае

❌ Неэффективен для больших сумм и большого количества номиналов

Решение 2: Динамическое программирование (bottom-up) 🚀

function coinChangeDP(coins, amount) {
  // dp[i] - минимальное количество монет для размена суммы i
  const dp = Array(amount + 1).fill(Infinity);
  
  // Базовый случай: для размена 0 нужно 0 монет
  dp[0] = 0;
  
  // Заполняем массив dp для всех сумм от 1 до amount
  for (let i = 1; i <= amount; i++) {
    // Перебираем все доступные монеты
    for (const coin of coins) {
      // Если можем использовать текущую монету
      if (i - coin >= 0) {
        // Обновляем минимальное количество монет
        dp[i] = Math.min(dp[i], dp[i - coin] + 1);
      }
    }
  }
  
  // Если dp[amount] осталось Infinity, значит разменять невозможно
  return dp[amount] === Infinity ? -1 : dp[amount];
}

Характеристики:

✅ Оптимальная временная сложность O(amount × n), где n - количество номиналов

✅ Находит гарантированно минимальное количество монет

✅ Работает для любых наборов монет

❌ Требует O(amount) дополнительной памяти

Решение 3: Рекурсия с мемоизацией (top-down DP) 🔧

function coinChangeMemization(coins, amount) {
  // Кэш для хранения промежуточных результатов
  const memo = {};
  
  function dp(remaining) {
    // Базовый случай
    if (remaining === 0) return 0;
    if (remaining < 0) return -1;
    
    // Проверяем, есть ли результат в кэше
    if (memo[remaining] !== undefined) {
      return memo[remaining];
    }
    
    let minCoins = Infinity;
    
    // Перебираем все монеты
    for (const coin of coins) {
      const result = dp(remaining - coin);
      
      // Если можно разменять оставшуюся сумму
      if (result >= 0) {
        minCoins = Math.min(minCoins, result + 1);
      }
    }
    
    // Сохраняем результат в кэше
    memo[remaining] = minCoins === Infinity ? -1 : minCoins;
    
    return memo[remaining];
  }
  
  return dp(amount);
}

Преимущества и недостатки:

✅ Более понятная логика по сравнению с итеративным DP

✅ Эффективно использует мемоизацию для избежания повторных вычислений

✅ Временная сложность O(amount × n)

❌ Может привести к переполнению стека для очень больших сумм

Решение 4: BFS (поиск в ширину) 📊

function coinChangeBFS(coins, amount) {
  if (amount === 0) return 0;
  
  // Отсортируем монеты для оптимизации
  coins.sort((a, b) => a - b);
  
  // Очередь для BFS: [текущая сумма, количество использованных монет]
  const queue = [[0, 0]];
  
  // Множество для отслеживания посещенных сумм
  const visited = new Set();
  
  while (queue.length > 0) {
    const [currentAmount, count] = queue.shift();
    
    // Перебираем все возможные монеты
    for (const coin of coins) {
      const nextAmount = currentAmount + coin;
      
      // Если точно набрали нужную сумму
      if (nextAmount === amount) {
        return count + 1;
      }
      
      // Если можем продолжить добавлять монеты
      if (nextAmount < amount && !visited.has(nextAmount)) {
        visited.add(nextAmount);
        queue.push([nextAmount, count + 1]);
      }
    }
  }
  
  return -1; // Невозможно разменять
}

Особенности:

✅ Гарантированно находит минимальное количество монет

✅ Интуитивно понятная реализация с использованием BFS

✅ Хорошо подходит для задач с небольшими суммами

❌ Может быть менее эффективен по памяти, чем DP

Количество способов размена

Решение 1: Динамическое программирование 🌟

function coinChangeWaysDP(coins, amount) {
  // dp[i] - количество способов разменять сумму i
  const dp = Array(amount + 1).fill(0);
  
  // Базовый случай: есть 1 способ разменять 0 (не брать монет)
  dp[0] = 1;
  
  // Для каждого номинала монеты
  for (const coin of coins) {
    // Обновляем количество способов для всех сумм, которые можно разменять этой монетой
    for (let i = coin; i <= amount; i++) {
      dp[i] += dp[i - coin];
    }
  }
  
  return dp[amount];
}

Анализ решения:

✅ Оптимальная временная сложность O(amount × n)

✅ Элегантное решение с динамическим программированием

✅ Учитывает все возможные комбинации монет

✅ Работает корректно для всех входных данных

Решение 2: Рекурсия с мемоизацией для подсчета способов 🔍

function coinChangeWaysMemo(coins, amount) {
  const memo = {};
  
  function countWays(index, remaining) {
    // Базовые случаи
    if (remaining === 0) return 1; // Нашли один способ
    if (remaining < 0 || index >= coins.length) return 0;
    
    // Проверяем кэш
    const key = `${index}:${remaining}`;
    if (memo[key] !== undefined) {
      return memo[key];
    }
    
    // Рекурсивно считаем способы:
    // 1. Включаем текущую монету
    // 2. Пропускаем текущую монету
    const includeCurrentCoin = countWays(index, remaining - coins[index]);
    const excludeCurrentCoin = countWays(index + 1, remaining);
    
    memo[key] = includeCurrentCoin + excludeCurrentCoin;
    return memo[key];
  }
  
  return countWays(0, amount);
}

Характеристики:

✅ Более интуитивный рекурсивный подход

✅ Эффективно работает с мемоизацией

❌ Менее эффективен по памяти из-за хранения состояний (index, remaining)

❌ Может привести к переполнению стека для больших сумм

Разменять с ограниченным запасом монет

Решение: Динамическое программирование с ограничениями 🔧

function coinChangeLimited(coins, counts, amount) {
  // dp[i] - минимальное количество монет для размена суммы i
  const dp = Array(amount + 1).fill(Infinity);
  
  // Для каждой суммы храним использованные монеты
  const usedCoins = Array(amount + 1).fill().map(() => ({}));
  
  // Базовый случай
  dp[0] = 0;
  
  for (let i = 1; i <= amount; i++) {
    for (let j = 0; j < coins.length; j++) {
      const coin = coins[j];
      
      if (i - coin >= 0 && dp[i - coin] !== Infinity) {
        // Проверяем, не превышаем ли лимит для текущей монеты
        const prevUsed = usedCoins[i - coin][coin] || 0;
        
        if (prevUsed < counts[j]) {
          // Можем использовать эту монету
          if (dp[i - coin] + 1 < dp[i]) {
            dp[i] = dp[i - coin] + 1;
            
            // Копируем информацию об использованных монетах
            usedCoins[i] = { ...usedCoins[i - coin] };
            usedCoins[i][coin] = (usedCoins[i][coin] || 0) + 1;
          }
        }
      }
    }
  }
  
  if (dp[amount] === Infinity) {
    return { possible: false, coinCount: -1, usedCoins: null };
  }
  
  return {
    possible: true,
    coinCount: dp[amount],
    usedCoins: usedCoins[amount]
  };
}

Преимущества и недостатки:

✅ Учитывает ограничения на количество монет каждого номинала

✅ Возвращает не только количество монет, но и их состав

❌ Более сложная реализация и логика

❌ Требует больше памяти для хранения информации об использованных монетах

Интуиция за динамическим программированием в задаче о монетах

Ключевая идея DP подхода к задаче о размене монет основана на принципе оптимальной подструктуры:

1. Для минимального количества монет:

   • Если мы знаем минимальное количество монет для размена суммы S - c для каждого номинала c, то минимальное количество для суммы S будет равно 1 + min(dp[S-c]) для всех доступных номиналов.

2. Для количества способов размена:

   • Количество способов разменять сумму S равно сумме количества способов разменять S - c для каждого номинала c.

Это позволяет нам построить решение "снизу вверх", последовательно вычисляя оптимальные значения для всех сумм от 1 до целевой.

Рекомендации по решению 💡

1. Выбор метода решения:

   • 🚀 Для минимального количества монет предпочтительнее использовать DP
   • 📝 Для количества способов размена также эффективно работает DP
   • 🧮 В случае ограничений на запас монет, модифицируйте DP с отслеживанием использованных монет

2. Важные моменты:

   • 📝 Правильно определите базовые случаи
   • 🔄 Учитывайте порядок обработки монет (для количества способов важен порядок перебора)
   • 📊 Внимательно следите за граничными условиями и случаем, когда размен невозможен

Распространённые ошибки

1. 🤦‍♂️ Неправильное определение базового случая (для суммы 0)
2. 😅 Путаница в порядке перебора монет и сумм в DP
3. 🐛 Ошибки при обработке случая, когда размен невозможен
4. 😕 Неоптимальное использование памяти при мемоизации

Визуализация алгоритма DP для минимального количества монет

Рассмотрим пример с монетами [1, 2, 5] и суммой 11:

Таблица DP будет заполняться так:

Сумма:   0  1  2  3  4  5  6  7  8  9  10  11
dp[i]:   0  1  1  2  2  1  2  2  3  3  2   3

Процесс заполнения:

• dp[0] = 0 (базовый случай)
• dp[1] = 1 (одна монета номиналом 1)
• dp[2] = 1 (одна монета номиналом 2)
• dp[3] = 2 (монеты 1+2 или три монеты по 1, выбираем минимум: 2)
• dp[4] = 2 (две монеты по 2 или четыре по 1, выбираем минимум: 2)
• dp[5] = 1 (одна монета номиналом 5)
• ...
• dp[11] = 3 (минимум из: dp[10]+1, dp[9]+1, dp[6]+1 = min(2+1, 3+1, 2+1) = 3)

Ответ: минимальное количество монет для размена 11 равно 3 (можно использовать 5+5+1).

Визуализация алгоритма DP для количества способов размена

Для монет [1, 2, 5] и суммы 5:

Начальное состояние:
dp = [1, 0, 0, 0, 0, 0]  (dp[0] = 1, остальные = 0)

После обработки монеты номиналом 1:
dp = [1, 1, 1, 1, 1, 1]  (для каждой суммы есть 1 способ с монетами по 1)

После обработки монеты номиналом 2:
dp = [1, 1, 2, 2, 3, 3]  (добавляются способы с использованием монеты 2)

После обработки монеты номиналом 5:
dp = [1, 1, 2, 2, 3, 4]  (добавляется 1 способ для суммы 5 - одна монета 5)

Ответ: существует 4 способа разменять сумму 5 указанными монетами.

Оптимизации

Оптимизация порядка перебора монет

function coinChangeOptimized(coins, amount) {
  // Сортируем монеты по возрастанию для оптимизации
  coins.sort((a, b) => a - b);
  
  // Отфильтровываем монеты, превышающие сумму
  const filteredCoins = coins.filter(coin => coin <= amount);
  
  // Если нет подходящих монет, но сумма не нулевая
  if (filteredCoins.length === 0 && amount > 0) {
    return -1;
  }
  
  // Стандартное DP решение с отфильтрованными монетами
  // ...
}

Оптимизация памяти для больших сумм

function coinChangeSpaceOptimized(coins, amount) {
  // Используем массив только для текущего и предыдущего уровня
  // для задачи подсчета способов размена
  let prev = Array(amount + 1).fill(0);
  let curr = Array(amount + 1).fill(0);
  
  // Базовый случай
  prev[0] = 1;
  
  for (let i = 0; i < coins.length; i++) {
    // Копируем значения из предыдущего уровня
    for (let j = 0; j <= amount; j++) {
      curr[j] = prev[j];
    }
    
    // Обновляем текущий уровень
    for (let j = coins[i]; j <= amount; j++) {
      curr[j] += curr[j - coins[i]];
    }
    
    // Обновляем prev для следующей итерации
    [prev, curr] = [curr, prev];
  }
  
  return prev[amount];
}

Использование битовых операций для задачи достижимости

function coinChangeReachable(coins, amount) {
  // Используем битовый массив для отслеживания достижимых сумм
  // Бит i установлен, если сумма i достижима
  let reachable = 1n; // Бит 0 установлен (сумма 0 всегда достижима)
  
  for (const coin of coins) {
    // Для каждой достижимой суммы i, сумма i+coin также достижима
    reachable |= (reachable << BigInt(coin));
  }
  
  // Проверяем, установлен ли бит для целевой суммы
  return (reachable & (1n << BigInt(amount))) !== 0n;
}

Практические применения задачи о размене монет

1. Финансовые системы

Алгоритмы размена используются в:

• Банкоматах для оптимального выдачи купюр
• Кассовых аппаратах для расчета сдачи
• Платежных системах для минимизации транзакций

2. Планирование ресурсов

• Оптимальное распределение времени в планировании проектов
• Упаковка продуктов в стандартные контейнеры
• Планирование производственных циклов

3. Криптовалюты и блокчейн

• Оптимизация транзакций в UTXO-моделях (Bitcoin)
• Выбор оптимальных входов для формирования транзакций

Варианты задачи о монетах

Задача о сдаче с минимальным количеством монет

Классический вариант, который мы уже рассмотрели - найти минимальное количество монет для размена суммы.

Задача о выборе конкретного количества монет с целевой суммой

Выбрать ровно k монет, чтобы их сумма была равна целевой:

function coinSelectExactCount(coins, amount, k) {
  // dp[i][j][c] - возможно ли разменять сумму j
  // используя первые i монет и ровно c монет
  const dp = Array(coins.length + 1).fill().map(() => 
    Array(amount + 1).fill().map(() => 
      Array(k + 1).fill(false)
    )
  );
  
  // Базовый случай: сумма 0 достижима с 0 монет
  for (let i = 0; i <= coins.length; i++) {
    dp[i][0][0] = true;
  }
  
  for (let i = 1; i <= coins.length; i++) {
    for (let j = 0; j <= amount; j++) {
      for (let c = 0; c <= k; c++) {
        // Не берем текущую монету
        dp[i][j][c] = dp[i-1][j][c];
        
        // Берем текущую монету, если возможно
        if (c > 0 && j >= coins[i-1]) {
          dp[i][j][c] = dp[i][j][c] || dp[i-1][j-coins[i-1]][c-1];
        }
      }
    }
  }
  
  return dp[coins.length][amount][k];
}

Задача о минимальном количестве монет заданного типа

Найти минимальное количество монет для размена, при условии, что используются монеты только определенных типов:

function coinChangeWithConstraints(coins, requiredTypes, amount) {
  // requiredTypes - массив булевых значений, указывающих,
  // должна ли монета соответствующего типа использоваться
  
  // Находим все действительно доступные монеты
  const availableCoins = coins.filter((_, index) => !requiredTypes[index]);
  
  // Для каждой обязательной монеты проверяем, можно ли составить оставшуюся сумму
  let result = Infinity;
  
  // Функция для проверки всех комбинаций обязательных монет
  function backtrack(index, remainingAmount, usedCoins) {
    // Если остаток можно разменять доступными монетами
    if (remainingAmount === 0) {
      result = Math.min(result, usedCoins);
      return;
    }
    
    // Если перебрали все обязательные монеты
    if (index >= coins.length) {
      // Проверяем, можно ли разменять оставшуюся сумму доступными монетами
      const minAdditional = coinChangeDP(availableCoins, remainingAmount);
      
      if (minAdditional !== -1) {
        result = Math.min(result, usedCoins + minAdditional);
      }
      return;
    }
    
    // Если текущая монета не обязательна
    if (!requiredTypes[index]) {
      backtrack(index + 1, remainingAmount, usedCoins);
      return;
    }
    
    // Если текущая монета обязательна, нужно использовать хотя бы одну
    let count = 1;
    while (remainingAmount - coins[index] * count >= 0) {
      backtrack(index + 1, remainingAmount - coins[index] * count, usedCoins + count);
      count++;
    }
  }
  
  backtrack(0, amount, 0);
  
  return result === Infinity ? -1 : result;
}

Заключение

При решении задачи о размене монет важно помнить:

• 🤹‍♂️ Динамическое программирование - основной метод решения для большинства вариантов задачи
• 📊 Правильное определение состояний и переходов - ключ к эффективному DP
• 🧠 Важно учитывать особенности конкретного варианта задачи (минимальное количество, количество способов, ограничения)
• 🔄 Оптимизации по памяти и времени могут существенно улучшить производительность алгоритма

Эта задача является фундаментальной в алгоритмике и имеет множество практических применений: от банкоматов и кассовых аппаратов до систем планирования ресурсов и криптовалютных транзакций. Понимание различных подходов к её решению значительно расширяет алгоритмический арсенал программиста. 🌟