Recursion and Dynamic Programming

Coin Change (Bottom-Up)

Build a one-dimensional table where each amount stores the fewest coins needed to make it.

Algorithm

@steps

  1. Initialize dp[0] = 0 and all other amounts to an unreachable sentinel.
  2. Scan amounts from 1 through 6.
  3. For each coin, read the earlier cell dp[amount - coin] when it exists.
  4. Write the smallest candidate into the current amount.
  5. Print both the final answer and the full DP array. @end @complexity
  • Time: O(target * coin_count)
  • Space: O(target) @end
bottom-up dynamic programming `dp[a]` is solved from already-computed smaller amounts, so every table cell has a visible dependency.

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))

@end @output 2 [0, 1, 2, 1, 1, 2, 2] @end