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

Ruby DSA Implementation

basic.rb

def list_string(values)
  "[" + values.join(", ") + "]"
end

coins = [1, 3, 4]
target = 6
inf = target + 1
dp = Array.new(target + 1, inf)
dp[0] = 0
(1..target).each do |amount|
  coins.each do |coin|
    next if amount < coin
    candidate = dp[amount - coin] + 1
    dp[amount] = candidate if candidate < dp[amount]
  end
end
puts dp[target]
puts list_string(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.

Implementation notes

coins is the Ruby array [1, 3, 4], and target is the fixed value 6.
inf = target + 1 makes the unreachable sentinel 7 for this pinned input.
dp = Array.new(target + 1, inf) creates seven slots initialized to 7, then dp[0] = 0 seeds the zero-amount base case.
The outer loop uses the inclusive range (1..target), so amounts 1 through 6 are filled left to right.
For each amount, coins.each checks coin 1, then 3, then 4.
next if amount < coin is the bounds guard before reading dp[amount - coin].
candidate = dp[amount - coin] + 1 is written only when candidate < dp[amount].
The trace shows the table states ending at [0, 1, 2, 1, 1, 2, 2], with dp[6] = 2.
puts dp[target] prints the answer first, then list_string(dp) prints the full DP array.

Output

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