DSA · 1-D dynamic programming · #10

Coin Change

Module 13 · difficulty 3/5·⏱ 30:00starts on first keystroke

You are given an integer array `coins` representing coins of different denominations and an integer `amount` representing a total amount of money. Return the fewest number of coins needed to make up that amount. If that amount cannot be made up by any combination of the coins, return `-1`. You may assume that you have an infinite number of each kind of coin.

Examples

coins = [1,2,5], amount = 11 → 3 — 5 + 5 + 1
coins = [2], amount = 3 → -1
coins = [1], amount = 0 → 0
coins = [1,3,4], amount = 6 → 2 — 3 + 3 — greedy would pick 4+1+1

Constraints

· 1 <= coins.length <= 12
· 1 <= coins[i] <= 2^31 - 1
· 0 <= amount <= 10^4

Session phases

A · Clarify

B · Approach

C · Complexity

D · Edges

E · Code

F · Tradeoff

G · Score

Phase A — Clarify

Ask questions about input bounds, types, and edge constraints.

Ask the coach clarifying questions about the problem.

When you've covered this phase, advance to the next.