Coin Change (Bottom-Up)

Build a one-dimensional table where each amount stores the fewest coins needed to make it.

Algorithm

@steps

Initialize dp[0] = 0 and all other amounts to an unreachable sentinel.
Scan amounts from 1 through 6.
For each coin, read the earlier cell dp[amount - coin] when it exists.
Write the smallest candidate into the current amount.
Print both the final answer and the full DP array. @end @complexity

Time: O(target * coin_count)
Space: O(target) @end

bottom-up dynamic programming `dp[a]` is solved from already-computed smaller amounts, so every table cell has a visible dependency.

Java DSA Implementation

Basic.java

import java.util.Arrays;

public class Basic {
  static String listString(int[] values) {
    StringBuilder out = new StringBuilder("[");
    for (int i = 0; i < values.length; i++) {
      if (i > 0) out.append(", ");
      out.append(values[i]);
    }
    return out.append("]").toString();
  }
  public static void main(String[] args) {
    int[] coins = {1, 3, 4};
    int target = 6;
    int inf = target + 1;
    int[] dp = new int[target + 1];
    Arrays.fill(dp, inf);
    dp[0] = 0;
    for (int amount = 1; amount <= target; amount++) {
      for (int coin : coins) {
        if (amount >= coin) {
          int candidate = dp[amount - coin] + 1;
          if (candidate < dp[amount]) dp[amount] = candidate;
        }
      }
    }
    System.out.println(dp[target]);
    System.out.println(listString(dp));
  }
}

@end @output 2 [0, 1, 2, 1, 1, 2, 2] @end