Coin Change

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

Пример 1:

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

Пример 2:

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

Задача на LeetCode.

Решение #

Если просят найти минимум или максимум среди множества различных вариантов, первое, что приходит в голову — рекурсивный перебор, т.е. представить варианты в виде графа (или дерева, как частный случай) и запустить поиск в глубину (DFS).

Если построить дерево рекурсивных вызовов, аналогично задаче про камни, то станут видны повторяющиеся вычисления, т.к. узлы с одинаковыми значениями (и поддеревьями, которые из-за этого повторяются целиком в разных частях дерева). Это верный признак динамического программирования. Если писать рекурсивный вариант — нужно вкручивать кэш, то что называют “top-down approach”.

Вообще, такой вариант решения: сперва написать поиск в глубину, а после кэшировать — отлично работает.

В данном случае, я напишу “bottom-up approach”, т.е. когда зная решение для n мы переходим к решению для n + 1, начиная всё с базового случая.

В динамическом программировании важно правильно выбрать «это самое решение», обычно — это ровно то, что и спрашивается в задаче, но не всегда (тогда всё становится сложнее).

В данном случае, для каждого n будем спрашивать себя «какое минимальное количество монет нужно чтобы собрать сумму n?». Допустим мы знаем ответ для определённого n, какой будет переход к n + 1?

Рассмотрим пример из условия.

Мы знаем ответы на вопрос «минимальное количество монет необходимое, чтобы собрать определённую сумму» для всех предыдущих значений n. Надо попробовать добавить ещё одну монету из всех доступных вариантов и выбрать минимальное количество.

Варианты на рисунке выше:

В итоге, минимальное количество монет → одна, последний вариант. Его и запишем в качестве ответа и продолжим решать задачу дальше, пока не дойдём до указанного в условии amount.

/**
 * @param {number[]} coins
 * @param {number} amount
 * @return {number}
 */
var coinChange = function(coins, amount) {
  // инициализируем массив «ответов на вопрос задачи»,
  // длина до amount включительно,
  // изначальные значения — «условная бесконечность»,
  // т.е. невозможно большое количество монет,
  // что в данном случае просто на 1 больше нужной суммы
  const dp = new Array(amount + 1).fill(amount + 1);

  // базовый случай:
  // сколько бы ни было разных монет,
  // можно использовать ровно ноль штук
  // чтобы собрать сумму ноль
  dp[0] = 0;

  // начинаем решать задачу
  // постепенно поднимаясь наверх,
  // до нужной суммы включительно
  for (let i = 1; i <= amount; i++) {
    // перебираем все доступные монеты
    for (let c of coins) {
      // если текущее количество
      // в принципе позволяет использовать
      // указанную монету
      if (i - c >= 0) {
        // выбираем минимум среди всех вариантов
        dp[i] = Math.min(dp[i], dp[i - c] + 1);
      }
    }
  }
  // может так получиться, что из указанных монет
  // нужную сумму собрать невозможно,
  // в таком случае изначальное значение окажется
  // нетронутым — тогда надо вернуть -1, как
  // просили по условию
  return dp[amount] > amount ? -1 : dp[amount];
};

Отличное видео на YouTube с разбором данной задачи.

PS. Обсудить можно в телеграм-чате любознательных программистов. Welcome! 🤗

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