# LeetCode: Coin Change Solution

## Approach

Let

recursion(i, amount)
be the minimums of coins of
0..i
sum up to
amount

Base cases:

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

Choices:

• Take the coin
• Skip the coin
`.css-ds3kc{display:table-row;}.css-1t8atru{display:table-cell;opacity:0.5;padding-right:var(--chakra-space-6);-webkit-user-select:none;-moz-user-select:none;-ms-user-select:none;user-select:none;text-align:right;}1.css-2qghsv{display:table-cell;}recursion(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 06    if (remainingAmount < 0 || ithCoin < 0) return Infinity7
8    // query from cache9    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 result17    memo[ithCoin][remainingAmount] = res18
19    return res20  }21
22  const res = recursion(coins.length - 1, amount)23
24  return res === Infinity ? -1 : res25}```

Original problem

## Similar problems

Minimum Cost For Tickets

Maximum Value of K Coins From Piles

Minimum Number of Operations to Convert Time

## Tags

leetcode

dynamic programming

## Next Post

LeetCode: Check If A String Contains All Binary Codes Of Size K

Mar 13, 2021

Search Posts