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

Lua DSA Implementation

basic.lua

local function list_string(values)
  local parts = {}
  for i, value in ipairs(values) do parts[i] = tostring(value) end
  return "[" .. table.concat(parts, ", ") .. "]"
end

local coins = {1, 3, 4}
local target = 6
local inf = target + 1
local dp = {}
for i = 1, target + 1 do dp[i] = inf end
dp[1] = 0
for amount = 1, target do
  for _, coin in ipairs(coins) do
    if amount >= coin then
      local candidate = dp[amount - coin + 1] + 1
      if candidate < dp[amount + 1] then dp[amount + 1] = candidate end
    end
  end
end
print(dp[target + 1])
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.

Implementation notes

The pinned coins are local coins = {1, 3, 4} and the target is local target = 6.
Lua tables are 1-based in the list-style code here, so the source does not store logical dp[0] at numeric key 0.
Instead, amount 0 lives at dp[1], amount 1 lives at dp[2], and in general amount a lives at dp[a + 1].
local inf = target + 1 makes the unreachable sentinel 7, larger than any possible coin count for this target.
for i = 1, target + 1 do dp[i] = inf end fills seven table slots with 7, then dp[1] = 0 marks amount 0 as solved.
The trace starts from [0, 7, 7, 7, 7, 7, 7].
The outer loop is for amount = 1, target do; the inner loop uses ipairs(coins) to try coins 1, 3, then 4 in that order.
A coin is usable only when amount >= coin.
The recurrence reads the offset earlier amount with dp[amount - coin + 1] + 1 and writes the current amount at dp[amount + 1].
The trace updates the table to [0, 1, 7, 7, 7, 7, 7] for amount 1, then [0, 1, 2, 7, 7, 7, 7] for amount 2.
Amount 3 improves from coin 3, giving [0, 1, 2, 1, 7, 7, 7].
Amount 4 improves from coin 4, giving [0, 1, 2, 1, 1, 7, 7].
Amounts 5 and 6 finish as [0, 1, 2, 1, 1, 2, 7] and then [0, 1, 2, 1, 1, 2, 2].
The final answer is read from dp[target + 1], so target 6 prints 2.
list_string(dp) converts each table entry with tostring and joins them with table.concat, producing [0, 1, 2, 1, 1, 2, 2].

Output

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