Серия Simplify — Динамическое программирование № 2 — Разменная монета

Ссылка на Leetcode — https://leetcode.com/problems/coin-change/

Вы можете задать этот вопрос, если у вас есть некоторый опыт динамического программирования, в противном случае продолжайте.

Описание вопроса: Вам дан массив целых чисел coins, представляющих монеты разного номинала, и целое число amount, представляющее общую сумму денег.

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

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

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

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

  1. Как мы видим на изображении выше, есть много способов, которыми мы можем использовать доступные монеты, чтобы получить сумму 11. Для этого нам нужно найти наименьшее количество монет.
  2. Давайте выберем число от 0 до количества для анализа. Допустим, мы выбираем 4 (может быть что угодно, кроме крайностей). Чтобы получить сумму 4, мы должны перебрать монеты и принять решение, выбирать монету или нет. Один пример запуска показан ниже —
  • Монета — 1 Допустим, мы выбираем эту монету. Оставшаяся сумма 4 -1 = 3
  • Монета — 2 Допустим, мы не выбираем эту монету. Оставшаяся сумма снова 3, без изменений.
  • Монета 5 — Невозможно выбрать эту монету, потому что она больше оставшейся суммы. Остаток 3, без изменений.
  • Монета 1 снова — допустим, мы пропустим эту монету сейчас для нашего примера. Остаток 3, без изменений.
  • Монета 2 снова — мы выбираем это. Оставшаяся сумма 3–2 = 1
  • Coin5 снова — мы не можем выбрать это, потому что это больше, чем оставшаяся сумма. Остаток 1, без изменений.
  • Монета 1 в третий раз — Допустим, мы выбираем это. Оставшаяся сумма 1–1 = 0.

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

3. Теперь с этим мы получаем рекурсивное решение —

  • Первая строка показывает решение, в котором монету не выбирать. Поскольку мы не выбрали монету, сумма не уменьшается. И монета также удаляется во втором аргументе.
  • Вторая строка показывает решение, где мы выбираем монету. Поскольку мы выбрали монету, сумма уменьшается, и мы добавляем 1 к счету. И поскольку нам разрешено повторно использовать монеты, второй аргумент остается прежним.

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

/*
 This solution as such will not work for all cases. 
 Skipped edge case handling for simplicity 
*/

int count(int coins[], int M, int V) {
     // Base cases
     if (V==0) return 0;
     if (M<=0) return Integer.MAX_VALUE-1;
     
     // Recursive relation as we discussed above  
     return Math.min(count(coins, M-1, V), 1 + count(coins, M, V-coins[M-1]));
     
 }

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

class Solution {
   public int coinChange(int[] coins, int amount) {
        int dp[] = new int[amount + 1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;
        for (int i = 0; i < coins.length; i++) {
            
            for (int j = coins[i]; j < dp.length; j++) {
                if (dp[j - coins[i]] != Integer.MAX_VALUE) {
                    // This line below is from our recursive solution 
                    dp[j] = Math.min(dp[j], dp[j - coins[i]] + 1);
                }
            }
        }
        return dp[dp.length - 1] == Integer.MAX_VALUE ? -1 : dp[dp.length - 1];
    }
}

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

Следите за обновлениями и дополнительными пояснениями. Я начинающий писатель, буду постоянно обновлять свои посты, чтобы сделать их более понятными на основе комментариев или собственных мыслей о перечитывании :D

#HappyCoding