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

Python DSA Implementation

basic.py

def list_string(values):
    return "[" + ", ".join(str(v) for v in values) + "]"

coins = [1, 3, 4]
target = 6
inf = target + 1
dp = [inf] * (target + 1)
dp[0] = 0

for amount in range(1, target + 1):
    for coin in coins:
        if amount >= coin:
            candidate = dp[amount - coin] + 1
            if candidate < dp[amount]:
                dp[amount] = candidate

print(dp[target])
print(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.

Output

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

Implementation notes

Python stores the DP table in one mutable list. inf = target + 1 is an integer sentinel, and [inf] * (target + 1) fills each slot before dp[0] is overwritten with the base case 0.
The loop order is amount-first, then coin: for amount in range(1, target + 1) scans table indexes left to right, and for coin in coins tries each transition that passes if amount >= coin.
Candidate values are plain Python integers computed from dp[amount - coin] + 1; if candidate < dp[amount] mutates only the current list slot, preserving earlier DP cells for later amounts.
The replay-visible states are the in-place table updates from [0, 7, 7, 7, 7, 7, 7] through [0, 1, 2, 1, 1, 2, 2]. No per-cell objects are allocated beyond normal integer results and the one DP list managed by Python GC.