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. @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.

Bash DSA Implementation

basic.sh

list_string() {
  local out="["
  local first=1
  for value in "$@"; do
    if (( first )); then first=0; else out+=", "; fi
    out+="$value"
  done
  out+="]"
  printf '%s\n' "$out"
}

coins=(1 3 4)
target=6
inf=$((target + 1))
dp=()
for ((i=0; i<=target; i++)); do dp[i]=$inf; done
dp[0]=0
for ((amount=1; amount<=target; amount++)); do
  for coin in "${coins[@]}"; do
    if (( amount >= coin )); then
      candidate=$((dp[amount - coin] + 1))
      if (( candidate < dp[amount] )); then dp[amount]=$candidate; fi
    fi
  done
done
echo "${dp[target]}"
list_string "${dp[@]}"

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