Сложность: medium
Вам дан целочисленный массив 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 {
func change(_ amount: Int, _ coins: [Int]) -> Int {
var memo = Array(repeating: Array(repeating: -1, count: amount + 1), count: coins.count)
func numberOfWays(_ i: Int, _ amount: Int) -> Int {
if amount == 0 {
return 1
}
if i == coins.count {
return 0
}
if memo[i][amount] != -1 {
return memo[i][amount]
}
if coins[i] > amount {
memo[i][amount] = numberOfWays(i + 1, amount)
} else {
memo[i][amount] = numberOfWays(i, amount - coins[i]) + numberOfWays(i + 1, amount)
}
return memo[i][amount]
}
return numberOfWays(0, amount)
}
}Ставь 👍 и забирай 📚 Базу знаний