Class Change

java.lang.Object
topics.dynamic.Change
public class Change extends Object
Coin Change Problem — Dynamic Programming solution.

Given an amount of money and a set of coin denominations, finds the minimum number of coins needed to make exact change. Each denomination may be used any number of times (unbounded selection).

Why Greedy Fails

Greedily picking the largest coin that fits does not always give the minimum. For example, with amount=15 and coins=[1,6,4]: 

  Greedy:  6+6+1+1+1 = 5 coins
  Optimal: 6+4+4+1   = 4 coins  ← what DP finds

Why Dynamic Programming Works

The problem has optimal substructure: the minimum coins for amount j using denominations 0..i depends only on already-solved smaller sub-problems. It also has overlapping sub-problems: many intermediate amounts are recomputed in naive recursion, making memoisation worthwhile.

Recurrence Relation

  dp[i][j] = min(
    dp[i-1][j],              // skip coin type i
    1 + dp[i][j - coins[i]]  // use one more coin of type i (unbounded)
  )
  Base case: dp[0][j] = j   (only coins[0]=1 available)

Complexity

  • Time: O(amount × types) — fills the entire DP table
  • Space: O(amount × types) — the DP table itself (reducible to O(amount) with a rolling 1-D array)

Example Table

amount=15, coins=[1,6,4]: 

     j:  0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15
  [1]:   0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15
  [6]:   0  1  2  3  4  5  1  2  3  4  5  6  2  3  4  5
  [4]:   0  1  2  3  1  2  1  2  2  3  2  3  2  3  2  4  ← answer: 4
Author:
vicegd
See Also:

  • Constructor Details

    • Change

      public Change()

  • Method Details

    • change

      public int change(int amount, int[] coins)
      Finds the minimum number of coins needed to make exact change for amount.

      Uses bottom-up DP, building the solution table row by row. Each row i adds denomination coins[i] to the available set.

      Key difference from 0/1 knapsack: when taking coin i, the lookup is sol[i][j - coins[i]] (same row) instead of sol[i-1][...] (previous row), because each denomination can be reused as many times as needed.

      Algorithm Steps

      1. Initialise row 0: sol[0][j] = j (need j copies of the unit coin).
      2. For each coin type i from 1 to types-1:
        For each amount j from 0 to amount:
        • notPicking = sol[i-1][j]
        • picking = 1 + sol[i][j - coins[i]] (only if j >= coins[i])
        • sol[i][j] = min(notPicking, picking)
      3. Return sol[types-1][amount].

      Complexity

      • Time: O(amount × types)
      • Space: O(amount × types)
      Parameters:
      amount - the target amount (must be ≥ 0)
      coins - available denominations; coins[0] must be 1 to guarantee a solution always exists for any positive amount
      Returns:
      the minimum number of coins that sum exactly to amount