Coin Change

Medium📊 1D Dynamic ProgrammingArrayDynamic ProgrammingBreadth-First Search

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 that you need to make up that amount. If that amount of money 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.

Example 1:

Input: coins = [1,2,5], amount = 11
Output: 3
Explanation: 11 = 5 + 5 + 1

Example 2:

Input: coins = [2], amount = 3
Output: -1

Example 3:

Input: coins = [1], amount = 0
Output: 0

Constraints:

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

Pattern Recognition & Intuition

Why this is a 1D Dynamic Programming problem

📊

1D Dynamic Programming

Cache sub-problem answers — never solve the same problem twice.

1D DP stores answers to sub-problems in a 1D array (or a few variables). Each dp[i] represents the answer to a sub-problem of size i. The solution to the full problem is built bottom-up from these smaller answers, eliminating the exponential redundancy of naive recursion.

MENTAL MODEL

Define dp[i] clearly ("what does it mean?"), identify the recurrence relation dp[i] = f(dp[i-1], dp[i-2], …), handle base cases.

INTUITION

Imagine you're climbing stairs. The number of ways to reach step n is ways(n-1) + ways(n-2). If you compute ways(n-1) and ways(n-2) independently by recursion, you recompute ways(1), ways(2), … dozens of times. DP caches them so each is computed exactly once.

SIGNALS — WHEN TO USE THIS PATTERN

"Number of ways to…", "minimum cost to…", "maximum profit from…"
Decisions at each step that depend on prior decisions
Overlapping subproblems: the same sub-problem is solved multiple times in recursion
"You can do X or Y at each step" — classic two-choice DP
Optimal substructure: the optimal answer for i uses optimal answers for i-1, i-2, etc.

Approaches & Trade-offs

From brute force to optimal — understand every step of the journey

BRUTE FORCE

Brute Force

⏱ O(2ⁿ) — exponential due to recomputation of overlapping sub-problems💾 O(n) recursion stack

✦ OPTIMAL

Optimal

⏱ O(n) — each state computed exactly once💾 O(n) for the array; O(1) with space optimization

Build the dp array from smallest sub-problems to largest. No recursion — just a loop.

ALGORITHM STEPS

Identify the DP state: dp[i] = answer for sub-problem i
Initialize base cases: dp[0], dp[1], …
Loop i from 2 to n, computing dp[i] from earlier values
Return dp[n] as the final answer
Space-optimize: if dp[i] only uses dp[i-1] and dp[i-2], store just two variables

TIME

O(n) — each state computed exactly once

SPACE

O(n) for the array; O(1) with space optimization

Always define dp[i] clearly FIRST, then figure out the recurrence.

def climb_stairs(n):
    if n <= 1: return 1
    prev2, prev1 = 1, 1          # dp[0], dp[1]
    for i in range(2, n + 1):
        curr = prev1 + prev2     # dp[i] = dp[i-1] + dp[i-2]
        prev2, prev1 = prev1, curr
    return prev1

Key Insight & Common Pitfalls

THE "AHA" MOMENT

The hardest part of DP is NOT the code — it's the definition of dp[i]. Ask yourself: "What is the sub-problem at index i?" Once that's crystal clear, the recurrence relation usually follows naturally. Common definitions: dp[i] = "max sum ending at i", "min cost to reach i", "number of ways to reach i". Write the definition as a comment before writing any code.

COMMON MISTAKES

✕Undefined dp[i]: not being precise about what dp[i] represents
✕Missing base cases: dp[0] or dp[1] initialized incorrectly
✕Off-by-one: dp has length n vs n+1 — be careful with 0-indexed vs 1-indexed
✕Trying to space-optimize before the O(n) solution works correctly

PRO TIPS

›Top-down with memo: add @functools.lru_cache(None) to your recursive function to auto-memoize
›If dp[i] depends only on the last 1-2 values, use rolling variables (O(1) space)
›"House Robber" pattern: dp[i] = max(dp[i-1], dp[i-2] + nums[i]) — skip or take
›Draw the recursion tree first, identify repeated sub-trees — that's the overlap to cache

Interactive Visualizer

Building 📊 1D Dynamic Programming Visualization

Generating visualization…