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.

Complexity

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

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

Visual walkthrough

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));
  }
}

The pinned coins are [1, 3, 4] and target is 6. The diagrams show the one-dimensional DP table becoming reachable from left to right.

Step 1 - Initialize reachable amount 0

dp[0] = 0; every other amount starts as the sentinel 7.

Step 2 - Early amounts become reachable

With coins 1, 3, and 4, amounts 1 through 4 fill as [1, 2, 1, 1].

Step 3 - Final answer at amount 6

dp[5] = 2 and dp[6] = 2, so the target needs two coins.

Output

2
[0, 1, 2, 1, 1, 2, 2]

Implementation notes

Java stores both coins and dp in primitive int[] arrays. dp is one contiguous array of target + 1 slots, so updates mutate indexed integer cells in place.
The unreachable sentinel is inf = target + 1, and Arrays.fill(dp, inf) initializes every amount before dp[0] = 0 writes the base case.
The loop order is amount-first, then coin: amount runs from 1 through target, and the enhanced for (int coin : coins) tries each transition only when amount >= coin.
candidate = dp[amount - coin] + 1 reads an earlier computed cell, which may still hold the sentinel in general; because the sentinel is only 7 here, adding one cannot approach int overflow. if (candidate < dp[amount]) then writes the smaller primitive value back into the same dp array.
The replay-visible table moves from [0, 7, 7, 7, 7, 7, 7] to [0, 1, 2, 1, 1, 2, 2]. Allocation is mainly the two arrays plus the StringBuilder, its backing storage, and the returned String used for deterministic output, all managed by JVM GC.