Coin Change

Given coin denominations and an amount, return the fewest coins needed to make that amount, or -1 if it's impossible. Each coin can be used any number of times.

A way to picture it

You're a cashier who hates handing out lots of coins. For every amount from 1 upward, ask: if this coin were the last one I handed over, how few coins would the rest need? You already solved that smaller amount a moment ago.

How to approach it

fewest(a) = 1 + min over coins c ≤ a of fewest(a − c), with fewest(0) = 0. Amounts nothing can make stay at infinity.

Example

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

Complexity: O(amount · coins) time and O(amount) space. Each amount tries every coin once.

This page includes an animated walkthrough, Java and Python solutions, and a question to check your understanding.