Coin Change

L9 Hard Dynamic Programming

Concept

For "fewest coins to make an amount", think in amount space: the answer for an amount uses the answer for smaller amounts, one coin smaller.

Given coin denominations coins (unlimited supply of each) and an amount, return the fewest number of coins that add up to exactly amount, or -1 if it is impossible.

Examples

▸ coins = [1, 2, 5], amount = 11

→ 3

▸ coins = [2], amount = 3

→ -1

▸ coins = [1], amount = 0

→ 0

Progressive Hints

Hint 1 · Nudge

The fewest coins for an amount is one coin plus the best known result for the remainder.

Hint 2 · Plan

Let dp[a] be the fewest coins that make amount a, starting from a large sentinel, with dp[0] = 0. For each amount, try every coin and relax: dp[a] = 1 + the smallest dp[a - coin] over usable coins. If dp[amount] stayed at the sentinel, return -1.

Hint 3 · Approach

dp = array of size amount + 1 filled with a large value; dp[0] = 0. For each amount a from 1 up: for each coin at most a, update dp[a] = min(dp[a], 1 + dp[a - coin]). Return -1 if dp[amount] is still large.

Output

// Run your code to see the output here.