Hints — p57 Coin Change

Hint 1. Greedy (“always largest coin first”) is wrong. Counter-example: coins=[1,3,4], amount=6 → greedy gives 4+1+1=3 coins, optimal is 3+3=2 coins.

Hint 2. Define dp[a] = min coins to make amount a. Base: dp[0] = 0. Transition: every solution for a ends with some coin c, so dp[a] = 1 + min(dp[a - c]) over coins c <= a.

Hint 3. Use a sentinel for “impossible” — float('inf') or amount + 1. After the DP, return dp[amount] if it’s a real value, else -1.

Hint 4. Alternative framing: BFS on a state graph. Nodes = amounts; edges from a to a + c for each coin c. Shortest path from 0 to amount = answer. Same complexity, different mental model — useful when state space is sparse.

Hint 5. Two loop orders both work for minimum coins; but for LC 518 (count of combinations) the outer loop must be over coins to avoid double-counting permutations. Don’t generalize blindly.

If stuck: see solution.py.