Задача: 518. Coin Change II
Вам дан целочисленный массив coins, представляющий монеты разных номиналов, и целое число amount, представляющее общую сумму денег.
Верните количество комбинаций, которые составляют эту сумму. Если эту сумму нельзя составить никакой комбинацией монет, верните 0.
Предположим, что у вас есть бесконечное количество каждой монеты.
Ответ гарантированно вписывается в знаковое 32-битное целое число.
Пример:
Input: amount = 5, coins = [1,2,5]
Output: 4
Explanation: there are four ways to make up the amount:
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1
👨💻 Алгоритм:
1⃣Создайте двумерный массив memo с n строками и amount + 1 столбцами. Инициализируйте значения -1, чтобы указать, что подзадача еще не решена. Реализуйте рекурсивный метод numberOfWays, который принимает два параметра: индекс i текущей рассматриваемой монеты и оставшуюся сумму, которую нужно составить. Он возвращает количество способов составить сумму, используя монеты, начиная с индекса i до последней монеты.
2⃣Если amount == 0, верните 1. Мы можем выбрать один способ, не выбирая ни одной монеты, чтобы составить сумму 0. Если i == n, у нас не осталось монет для составления суммы, верните 0. Если эта подзадача уже решена, т.е. memo[i][amount] != -1, верните memo[i][amount]. Если значение текущей монеты превышает сумму, мы не можем её использовать. Рекурсивно вызовите numberOfWays(i + 1, amount), присвойте результат memo[i][amount] и верните его.
3⃣В противном случае, добавьте общее количество способов составить сумму, как выбирая текущую монету, так и игнорируя её. Сложите значения numberOfWays(i, amount - coins[i]) и numberOfWays(i + 1, amount), сохраните результат в memo[i][amount] и верните его. Верните numberOfWays(0, amount), ответ на исходную задачу.
😎 Решение:
class Solution {
public int change(int amount, int[] coins) {
int[][] memo = new int[coins.length][amount + 1];
for (int i = 0; i < coins.length; i++) {
Arrays.fill(memo[i], -1);
}
return numberOfWays(0, amount, coins, memo);
}
private int numberOfWays(int i, int amount, int[] coins, int[][] memo) {
if (amount == 0) {
return 1;
}
if (i == coins.length) {
return 0;
}
if (memo[i][amount] != -1) {
return memo[i][amount];
}
if (coins[i] > amount) {
memo[i][amount] = numberOfWays(i + 1, amount, coins, memo);
} else {
memo[i][amount] = numberOfWays(i, amount - coins[i], coins, memo) + numberOfWays(i + 1, amount, coins, memo);
}
return memo[i][amount];
}
}👉Новости 👉Платформа