LeetCode: Coin Change Solution

Approach

Let

be the minimums of coins of sum up to

Base cases:

• amount
  is
  0
• amount
  is below
  0
  or no coin left

Choices:

• Take the coin
• Skip the coin

1recursion(i, amount) = min(takeCoin(i, amount - valueOf(i)), skipCoin(i, amount))

Implementation

1var coinChange = function (coins, amount) {
2  let memo = Array.from({ length: coins.length }, _ => Array(amount).fill(null))
3
4  const recursion = (ithCoin, remainingAmount) => {
5    if (remainingAmount === 0) return 0
6    if (remainingAmount < 0 || ithCoin < 0) return Infinity
7
8    // query from cache
9    if (memo[ithCoin][remainingAmount] != null)
10      return memo[ithCoin][remainingAmount]
11
12    const takeCoin = 1 + recursion(ithCoin, remainingAmount - coins[ithCoin])
13    const skipCoin = recursion(ithCoin - 1, remainingAmount)
14    const res = Math.min(takeCoin, skipCoin)
15
16    // cache the result
17    memo[ithCoin][remainingAmount] = res
18
19    return res
20  }
21
22  const res = recursion(coins.length - 1, amount)
23
24  return res === Infinity ? -1 : res
25}

References

Original problem

Similar problems

Minimum Cost For Tickets

Maximum Value of K Coins From Piles

Minimum Number of Operations to Convert Time