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

SQL DSA Implementation

basic.sql

CREATE TEMP TABLE coins(value INTEGER);
INSERT INTO coins VALUES (1), (3), (4);
CREATE TEMP TABLE dp(amount INTEGER PRIMARY KEY, value INTEGER);
INSERT INTO dp VALUES (0, 0), (1, 7), (2, 7), (3, 7), (4, 7), (5, 7), (6, 7);
UPDATE dp SET value = (SELECT MIN(prev.value + 1) FROM coins JOIN dp AS prev ON prev.amount = 1 - coins.value WHERE 1 >= coins.value) WHERE amount = 1;
UPDATE dp SET value = (SELECT MIN(prev.value + 1) FROM coins JOIN dp AS prev ON prev.amount = 2 - coins.value WHERE 2 >= coins.value) WHERE amount = 2;
UPDATE dp SET value = (SELECT MIN(prev.value + 1) FROM coins JOIN dp AS prev ON prev.amount = 3 - coins.value WHERE 3 >= coins.value) WHERE amount = 3;
UPDATE dp SET value = (SELECT MIN(prev.value + 1) FROM coins JOIN dp AS prev ON prev.amount = 4 - coins.value WHERE 4 >= coins.value) WHERE amount = 4;
UPDATE dp SET value = (SELECT MIN(prev.value + 1) FROM coins JOIN dp AS prev ON prev.amount = 5 - coins.value WHERE 5 >= coins.value) WHERE amount = 5;
UPDATE dp SET value = (SELECT MIN(prev.value + 1) FROM coins JOIN dp AS prev ON prev.amount = 6 - coins.value WHERE 6 >= coins.value) WHERE amount = 6;
SELECT value FROM dp WHERE amount = 6;
SELECT '[' || group_concat(value, ', ') || ']' FROM dp ORDER BY amount;

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]