1D DP

Coin Change

Find minimum coins to make amount. For each amount from 1 to target: try every coin denomination. dp[amount] = 1 + min(dp[amount − coin]) for each coin that fits. Start dp[0] = 0 (zero coins for zero amount).

O(n * amount)

O(amount)

How It Works

Coin Change asks for the minimum number of coins that sum to a target amount. Define dp[a] as the fewest coins needed for amount a, with dp[0] = 0. For each amount from 1 to the target, try every coin denomination c: if c fits, dp[a] can be 1 + dp[a - c]. Taking the minimum over all coins explores every combination implicitly, while a greedy largest-coin strategy fails on systems like {1, 3, 4} for amount 6.

The table has O(amount) states and each state examines all k coins, giving O(amount × k) time and O(amount) space. Unreachable amounts stay at a sentinel value like infinity, and the final answer is -1 if dp[target] was never improved.

Step-by-Step Visualization

Min coins for amount 6. Coins: [1, 3, 4]

∞

dp[0]0

1/3

Code

Java

static int coinChange(int[] coins, int amount) {
  int[] dp = new int[amount + 1];
  Arrays.fill(dp, Integer.MAX_VALUE);
  dp[0] = 0;

  for (int i = 1; i <= amount; i++) {
    for (int coin : coins) {
      if (coin <= i && dp[i - coin] != Integer.MAX_VALUE)
        dp[i] = Math.min(dp[i], dp[i - coin] + 1);
    }
  }
  return dp[amount] == Integer.MAX_VALUE ? -1 : dp[amount];
}
// coinChange(new int[]{1,3,4}, 6) → 2 (3+3)

Tips & Gotchas

1dp[i] = min coins to make amount i

2For each coin, dp[i] = min(dp[i], dp[i - coin] + 1)

3Initialize dp[0]=0, rest = Infinity

Practice Problems

1Coin Change
2Coin Change II
3Perfect Squares
4Minimum Cost For Tickets

About the 1D DP Pattern

The state is a single variable (usually an index). Each dp[i] depends on a few previous values like dp[i−1] or dp[i−2]. Often you can optimize space by keeping only the last 2-3 values instead of the whole array.

Key insight

The framework: 1) Define state (what changes between subproblems). 2) Write recurrence relation. 3) Identify base cases. 4) Decide iteration order. Most DP is either 1D, 2D, or interval-based.

Common Dynamic Programming Interview Problems

Climbing Stairs
Coin Change
Longest Common Subsequence
0/1 Knapsack
Edit Distance
House Robber
Longest Increasing Subsequence
Word Break

Frequently Asked Questions

Why can't I just use the biggest coin first?

Greedy works for canonical currencies like US denominations but fails in general. With coins {1, 3, 4} and target 6, greedy picks 4+1+1 (three coins) while the optimum is 3+3 (two coins). DP considers every combination, so it is always correct.

What changes between counting combinations and minimizing coins?

Minimizing coins takes min over choices and the loop order does not matter. Counting distinct combinations (Coin Change II) sums over choices and must iterate coins in the outer loop so each combination is counted once regardless of coin order.

How do I detect an impossible amount?

Initialize every dp cell except dp[0] to a value larger than any real answer, such as amount + 1. If dp[target] still holds that sentinel after filling the table, no combination of coins reaches the target and you return -1.