Число способов разменять деньги

Задача. Надо разменять n рублей. У вас есть монеты номиналами [d1, d2, …, dm] в неограниченном количестве. Нужно найти число способов, которыми можно разменять изначальные n рублей.
Например:
Надо разменять 6 рублей.
И даны номиналы: [1, 5]. Это значит у вас есть в неограниченном количестве монеты номиналами 1 и 5 рублей.
Вы можете разменять 6 рублей двумя способами: шесть раз по рублю или 1 рубль + 5 рублей.

Решение. Для решения будем использовать динамическое программирование. Очень часто, когда в формулировке задачи вы встречаете: “число способов ..”, “найти минимальное …”, “найти максимальное …”, то это хороший признак того, что эта задача может быть на динамическое программирование.

Динамическое программирование это способ решения алгоритмическое задачи путем ее разбиения на подзадачи. Классический пример — это числа Фибоначчи. Задача нахождения n числа Фибоначчи формулируется через числа Фибоначчи n-1 и n-2. Fn = Fn-1 + Fn-2.

Есть два подхода в динамическом программировании:

1. Top-down. Рекурсивное с мемоизацией (используем кэш, чтобы не решать уже решенные подзадачи несколько раз). Например, рекурсивное решение для задачи про числа Фибоначчи. f(n) = f (n — 1) + f (n-2).

2. Bottom-up. Сначала решаем подзадачи и постепенно идем к общей задачи. Итеративное решение, в котором мы храним уже вычесленные результаты. Обычно это одномерный или многомерный массив. Для чисел Фибоначчи это последовательное итеративное вычисление всех чисел Фибоначчи начиная с первого и сохранением промежуточных значений в переменных или массиве.

Вернемся к задаче. Будем использовать Bottom-up подход. Промежуточные результаты будем хранить в двумерном массиве dp.

dp[i][j] — означает число способов разменять i рублей используя первые j монет (используя монеты номиналами от d0 до dj).

Тогда решением будет dp[n][m]. Это и есть число способов разменять n рублей используя монеты номиналами от d0 до dm. Что и спрашивается в задаче.

Хорошо. Но как нам заполнять этот двумерный массив?

Для этого нужно разбить задачу на подзадачи и установить связь между ними. Как в задаче про числа Фибоначчи (Fn = Fn-1 + Fn-2).

В нашем случае это можно сформулировать так: Число способов разменять i рублей используя первые j номиналов монет равно числу способов разменять i рублей не используя монету номиналом dj плюс числу способов разменять i — dj рублей (деньги минус номинал монеты) используя все номиналы до dj включительно.

Или в виде кода это:

dp[i][j] = dp[i][j — 1] + dp[i — coins[j]][j].

Т.е. мы представили задачу через две подзадачи: не используя монету номиналом coins[j] и используя такую монету хотя бы один раз (которая в свою очередь сводится к размену меньшего числа денег на номинал монеты).

Давайте посмотрим на примере:

Пусть нам надо разменять 5 рублей. И у нас есть монеты номиналами: [1, 2, 5].

По нашей формуле это будет: dp[5][3] = dp[5][2] + dp[5–5][3].

dp[5][2] — число способов разменять 5 рублей используя монеты 1 и 2 (3 способа: 1 + 1 + 1 + 1 + 1, 2 + 2 + 1, 2 + 1 + 1 + 1). dp[5][2] в свою очередь равно = dp[5][1] + dp[5–2][2] = dp[5][1] + dp[3][2]. dp[5][1] — число способов разменять 5 рублей имея только монету номиналом 1 (такой только один способ 1 + 1 + 1 + 1 + 1). dp[3][2] — число способов разменять 3 рубля имея монеты номиналами 1 и 2 (два способа: 1 + 1 + 1 и 2 + 1) и т.д.

dp[0][3] — число способов разменять 0 рублей используя монеты 1, 2, 5. Нам нужно установить базовые значения для случая 0 рублей (как и в задаче Фибоначчи нужно установить первые значения чисел Фибоначчи). Правильным базовым значением для нас будет 1. Т.е. всю первую строку (которая соответствует 0 рублей), нужно инициализировать единицами. Число разменять 0 рублей всегда будет равно одному.

Давайте посмотрим как будет заполняться наша матрица по шагам на примере.

Пусть надо разменять 5 рублей имея монеты 1, 2, 5. Строки в нашей матрице это число денег, которые надо разменять. Столбцы это номиналы монет.

Инициализируем первую строку единичками, что соответствую базовому случаю, когда надо разменять 0 рублей.

Теперь посмотрим на первый столбец. По нашей формуле:

dp[i][j] = dp[i][j — 1] + dp[i — coins[j]][j].

dp[i][0] = dp[i][-1] + dp[i-coins[0]][0]. Чтобы не выходить на пределы матрицы нужно добавить несколько проверок, тогда:

dp[i][0] = (i ≥ coins[j]) ? dp[i — coins[j]][0] : 0.

После заполнения первого столбца:

Ну действительно, разменять 1, 2, 3, 4, 5 рублей имея монету номиналом 1 рубль можно только одним способом.

Заполним вторую строку используя формулу:

dp[i][j] = dp[i][j — 1] + (i ≥ coins[j]) ? dp[i — coins[j]][j] : 0.

Т.е. будем суммировать значение в из предыдущего столбца (j-1) и из строки i-coins[j].

Тоже самое проделаем для всех остальных строк.

На картинке я также показал для одного из значений суммой каких элементов он является.

Ответ в данном примере будет 4.

Код решения:

      public int change(int amount, int[] coins) {
          if (amount == 0) {
           return 1;
          }

          if (coins.length == 0) {
           return 0;
          }

          int[][] dp = new int[amount + 1][coins.length];

          //Заполняем первую строку
          Arrays.fill(dp[0], 1);

          //Заполняем первый столбец 
          for (int i = 1; i <= amount; i++) {
              dp[i][0] = (i < coins[0]) ? 0 : dp[i - coins[0]][0];
          }


          //Вычисляем все остальные значения в матрице
          for (int i = 1; i <= amount; i++) {
              for (int j = 1; j < coins.length; j++) {
                  dp[i][j] = dp[i][j-1] + ( (i < coins[j]) ? 0 : dp[i - coins[j]][j] );
              }
          }

          return dp[amount][coins.length - 1];
      }

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

Также эту задачу можно решить использую Top-down подход через рекурсию с мемоизацией.