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

Swift DSA Implementation

basic.swift

func listString(_ values: [Int]) -> String {
    "[" + values.map(String.init).joined(separator: ", ") + "]"
}

let coins = [1, 3, 4]
let target = 6
let inf = target + 1
var dp = Array(repeating: inf, count: target + 1)
dp[0] = 0
for amount in 1...target {
    for coin in coins {
        if amount >= coin {
            let candidate = dp[amount - coin] + 1
            if candidate < dp[amount] {
                dp[amount] = candidate
            }
        }
    }
}
print(dp[target])
print(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.

Implementation notes

let coins = [1, 3, 4] and let target = 6 are immutable Swift [Int] and Int bindings for this replay.
let inf = target + 1 uses 7 as the unreachable sentinel; no valid answer for target 6 can need more than six 1 coins.
var dp = Array(repeating: inf, count: target + 1) creates seven mutable Int cells for amounts 0...6, then dp[0] = 0 seeds the base amount.
The outer loop for amount in 1...target fills the table left to right, so dp[amount - coin] is already available when amount >= coin.
The inner loop tries each coin and computes let candidate = dp[amount - coin] + 1; dp[amount] changes only when candidate < dp[amount].
The trace shows the table moving from [0, 7, 7, 7, 7, 7, 7] through amounts 1 and 2, then using coin 3 for dp[3] = 1 and coin 4 for dp[4] = 1.
For amount 6, coin 3 gives the best candidate 2, leaving the final table [0, 1, 2, 1, 1, 2, 2].
print(dp[target]) writes 2, then listString(dp) prints the full table as [0, 1, 2, 1, 1, 2, 2].

Output

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