Coin Change

Why it belongs on this sheet

This is a strong medium DP problem because it combines an intuitive recurrence with careful impossible-state handling.

Pattern

Minimum steps to each amount

Approach

Let dp[amount] be the minimum coins needed to form that amount. For each target amount, try every coin and extend from the previously solved smaller amount.

Java solution

import java.util.Arrays;

class Solution {
  public int coinChange(int[] coins, int amount) {
    int[] dp = new int[amount + 1];
    Arrays.fill(dp, amount + 1);
    dp[0] = 0;

    for (int current = 1; current <= amount; current++) {
      for (int coin : coins) {
        if (coin <= current) {
          dp[current] = Math.min(dp[current], dp[current - coin] + 1);
        }
      }
    }

    return dp[amount] > amount ? -1 : dp[amount];
  }
}

Complexity

• Time: O(amount * number of coins)
• Space: O(amount)

Interview note

Initializing with amount + 1 is a neat way to represent impossible states safely.