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.

Space-Optimized DP Transition

Instead of a full 2D matrix O(Amount * Types), we can use a 1D array O(Amount). For each coin, we update the array from left to right:

dp[j] = min( dp[j], 1 + dp[j - coin] )

Complexity Analysis

  • Time Complexity: O(Amount × Types) - We evaluate every coin against every sub-amount up to the target.
  • Space Complexity: O(Amount) - We only maintain the optimal solutions for the current amounts being processed.
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 1D DP table.
      Parameters:
      amount - The target monetary amount.
      coins - The available denominations. Must include 1 to guarantee a solution.
      Returns:
      The optimal (minimum) number of coins.
      Throws:
      IllegalArgumentException - if amount is negative, coins are null, or no 1-unit coin exists.