Class Change

java.lang.Object
topics.dynamic.change.Change
public class Change extends Object

Coin Change

Computes the absolute minimum number of coins required to make exact change for a specific target amount. Each denomination can be selected an unlimited number of times (Unbounded Knapsack variation).

Why Greedy Fails Here

A greedy approach (always picking the largest coin first) does not guarantee an optimal solution. For example, to make 15 with [1, 6, 4]:

  • Greedy: 6 + 6 + 1 + 1 + 1 = 5 coins.
  • DP Optimal: 6 + 4 + 4 + 1 = 4 coins.

Dynamic Programming Transition Matrix (2D)

This implementation constructs a 2D matrix of size N × (Amount+1). Row 0 represents having only the base coin available (base case: dp[0][j] = j). For each subsequent cell dp[i][j], we decide whether to:

  1. Skip the coin: Inherit the minimum from the row directly above: dp[i-1][j].
  2. Use the coin: Add 1 to the minimum for the remaining amount in the same row: 1 + dp[i][j - coins[i]].

Note: Since each denomination can be reused, we look within the same row (unlike 0/1 Knapsack, which looks at the row above to prevent reuse).

Complexity Analysis

  • Time Complexity: O(N × Amount) - We evaluate every coin against every sub-amount up to the target.
  • Space Complexity: O(N × Amount) - Maintains the full historical state matrix for pedagogical clarity.
Author:
vicegd

  • Constructor Details

    • Change

      public Change()

  • Method Details

    • change

      public int change(int amount, int[] coins)
      Determines the minimum coins required for the target amount using a 2D DP matrix.
      Parameters:
      amount - The target monetary amount.
      coins - The available denominations. Must include 1 as the first element to guarantee a solution.
      Returns:
      The optimal (minimum) number of coins.
      Throws:
      IllegalArgumentException - if amount is negative, coins are null, or coins array is empty.