Coin Change

You have several coin values (positive integers). You may use as many of each coin as you want. Given a target amount A, find the smallest number of coins whose values add up to A. If it cannot be done, say so (in the code below, the caller checks the answer against a special “too big” value).

Example: coins {1, 3, 4}, A = 6. One option is 4 + 1 + 1 (three coins); another is 3 + 3 (two coins). The answer is 2.

Let dp(x) = minimum number of coins to make amount x.

Think one step at a time. Suppose the last coin you use has value c. Then the other coins must make x − c, which needs dp(x − c) coins. So this choice uses dp(x − c) + 1 coins in total.

You do not know which c is best, so try every coin that does not overshoot (c ≤ x) and pick the smallest result:

Small example: dp(6) with coins 1, 3, 4:

• use 1 last → dp(5) + 1
• use 3 last → dp(3) + 1
• use 4 last → dp(2) + 1

Take the minimum of those three numbers (after you know dp for the smaller amounts).

Store memo[0] … memo[A]. If memo[x] is already filled, return it instead of recomputing.

Only amounts 0 … A appear, so there are A + 1 states. Each state tries each coin once → O(A × number of coins) time and O(A) space.

Explanation: Amount zero needs no coins.

If no coin fits x, or every recursive branch is “impossible,” then dp(x) has no solution. In code we use a large integer INF for “impossible” so we can still take min safely.

Counting how many ways to make A (order does not matter) uses a two-parameter DP g(i, x) — different problem. This page only covers minimum coin count.

Recursive DP with memo:

Time: O(A · |coins|). Space: O(A).