Coin Change

Problem

Given an array coins of distinct coin denominations and a target amount, return the FEWEST number of coins needed to make exactly amount (unlimited supply of each denomination), or -1 if it's impossible. (LeetCode 322.)

Examples

Constraints

1 ≤ coins.length ≤ 12, 1 ≤ coins[i] ≤ 2³¹-1, 0 ≤ amount ≤ 10⁴.

Attempt it first

This is unbounded knapsack (this module's Knapsack-Style DP concept lesson) — each coin denomination can be reused without limit. Before opening anything, and crucially BEFORE reaching for DP at all: think through why the seemingly-obvious greedy strategy — "always use the largest coin that fits" — is WRONG in general, using the concrete counterexample the Greedy module (Module 22) raised: denominations {1, 3, 4}, target 6. Work out what greedy produces versus what the true optimum is, and only then think about the DP recurrence.