Medium

Coin Change

063

Given coin denominations and a target amount, return the fewest coins needed to make that amount. Each denomination may be reused. Return -1 when the amount cannot be formed.

EXAMPLES

Example 1

Input
{
  "coins": [
    1,
    2,
    5
  ],
  "amount": 11
}

Output
3

FUNCTION SHAPE

coins: intArrayamount: int→int

SOLUTION NOTE

Try all possibilities pattern. For each amount, try using each coin and take the minimum. Base case: 0 coins needed for amount 0.

Reveal reference solution +

pythonREFERENCE

def coinChange(self, coins: List[int], amount: int) -> int:
    @cache
    def dp(amt):
        if amt == 0: return 0
        if amt < 0: return inf
        return 1 + min((dp(amt - c) for c in coins), default=inf)

    res = dp(amount)
    return res if res != inf else -1

TimeO(amount × len(coins))

SpaceO(amount)

Open on LeetCode ↗