Проблема

Учитывая набор монет и сумму сдачи, которую нам нужно вернуть, нас просят вычислить количество способов, которыми мы можем вернуть правильную сдачу, учитывая наш набор монет.

Примечание. В нашем распоряжении неограниченное количество монет каждого типа.

Развитие интуиции

Самое наивное решение, к которому мы обычно приходим, - это перебирать все различные возможности. В данном случае это не лучшая идея. Во-первых, само зацикливание было бы нетривиальным. Нам пришлось бы учитывать множество разных ситуаций.

Хорошо, это начало. У нас есть идея решения, которое могло бы сработать, но сразу оно кажется беспорядочным и не похоже на решение, которое мне особенно понравилось бы кодировать. Можем ли мы использовать тот же подход к проверке всех возможностей, но с более чистой реализацией? Рекурсивные решения обычно позволяют писать более лаконичный код. Давай попробуем!

Рекурсивное решение

Давайте вернемся к нашему семинару по рекурсии. Как нам определить рекурсивную функцию?

  1. Определение функции - наша функция должна принимать параметры. Таким образом, мы всегда можем проверить значение этих параметров, чтобы проверить, достигли ли мы базового случая.
  2. Определение нашего базового случая. Что является тривиальным случаем, когда мы уже знаем решение проблемы.
  3. Уменьшите проблему - увеличивая / уменьшая наши параметры, которые передаются при каждом рекурсивном вызове функции. Если мы этого не сделаем, наша проблема никогда не будет решена, и мы войдем в бесконечный цикл.

Давайте начнем с размышлений о нашем базовом сценарии. Что было бы действительно легко решить? Как только мы это поймем, у нас будет более четкое представление о том, как должно выглядеть наше объявление функции.

Обработка базовых случаев

Случай 1:

Что, если сумма сдачи, которую мы должны вернуть, равна 0? Это просто, есть только 1 способ вернуть 0 центов. Мы вообще ничего не должны возвращать.

Случай 2:

Что, если нам нужно вернуть определенную сумму сдачи (сумма ›0), но у нас нет монет? В этом случае мы должны вернуть 0, b / c у нас ровно ноль способов вернуть сдачу.

Случай 3:

Что, если нам нужно вернуть отрицательную сумму сдачи? Это невозможно! Таким образом, мы можем вернуть 0 и в этом случае.

Наше определение функции

При анализе нашего базового случая мы достигли 3 простых случаев, которые мы знаем, как решить. Все они использовали количество монет в моем распоряжении и сумму, которую мне нужно вернуть. Кроме того, наша функция определенно должна принимать сам массив монет, чтобы нам было с чем работать :) Зная это, мы создадим функцию, которая принимает все 3 эти переменные в качестве аргументов. Должно получиться так:

function waysToReturnChangeRecursive(coins, numOfCoins, amount) {}

В общем, наша проблема пока выглядит так:

Делаем проблему меньше

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

Каковы разумные способы уменьшить проблему, чтобы мы могли в конечном итоге решить один из наших базовых случаев? Что ж, нам нужен способ уменьшить количество монет, которые мы в настоящее время используем, и сумму, которую мы должны вернуть в качестве сдачи.

Мы могли бы посмотреть на наш текущий coins, numOfCoins, amount статус для каждой доступной нам монеты и принять одно из следующих двух решений:

  1. Решаем использовать текущую монету. В этом случае мы можем вычесть amount — currentCoin, потому что мы выбрали нашу текущую монету как часть того, что я в конечном итоге верну как сдачу. Поскольку в нашем распоряжении неограниченное количество монет каждого типа, мы меняем только ту сумму сдачи, которую необходимо вернуть.
  2. Решаем не использовать текущую монету. В этом случае мы можем уменьшить numOfCoins,, потому что мы решили больше не использовать конкретную монету. Обратите внимание, что здесь мы не будем обновлять сумму.

В целом код будет выглядеть так:

Динамическое программирование

Хотя наше рекурсивное решение работает, оно является избыточным, потому что мы в конечном итоге вычисляем множество одних и тех же сценариев более одного раза. (Вспомните рисунок дерева Фибоначчи в классе). В основном мы делаем много ненужной работы. Можем ли мы сделать наше решение более эффективным?

Что, если бы мы сохранили все сделанные вычисления, чтобы при повторном появлении подзадачи мы могли проверить, вычислили ли мы ее уже или нет? Если бы мы его вычислили, мы могли бы просто использовать этот результат вместо вычисления дополнительных значений. Однако нам нужно будет сохранить все эти вычисления. Мы могли бы использовать массив! Итак, давайте возьмем логику нашей предыдущей рекурсивной реализации и объединим ее с нашим подходом к динамическому программированию. Всего должно понравиться:

Заключение

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

Вопросов? Вы можете связаться со мной в LinkedIn или написать мне по адресу [email protected] ❤