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

Go DSA Implementation

basic.go

package main

import (
  "fmt"
  "strings"
)

func listString(values []int) string {
  parts := make([]string, len(values))
  for i, value := range values {
    parts[i] = fmt.Sprintf("%d", value)
  }
  return "[" + strings.Join(parts, ", ") + "]"
}

func main() {
  coins := []int{1, 3, 4}
  target := 6
  inf := target + 1
  dp := make([]int, target + 1)
  for i := range dp {
    dp[i] = inf
  }
  dp[0] = 0
  for amount := 1; amount <= target; amount++ {
    for _, coin := range coins {
      if amount >= coin {
        candidate := dp[amount - coin] + 1
        if candidate < dp[amount] {
          dp[amount] = candidate
        }
      }
    }
  }
  fmt.Println(dp[target])
  fmt.Println(listString(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

Go stores coins := []int{1, 3, 4} and allocates the DP table with dp := make([]int, target + 1), giving entries for amounts 0 through 6.
inf := target + 1 is the unreachable sentinel. The for i := range dp loop fills every slot with 7, then dp[0] = 0 overwrites the base case.
The outer loop scans amount := 1; amount <= target; amount++; the inner for _, coin := range coins copies each coin value and only reads dp[amount-coin] after if amount >= coin.
Each candidate is dp[amount - coin] + 1; there is no separate overflow guard because the sentinel is small (7) and this checked input is fully reachable.
Updates mutate dp[amount] in place only when candidate < dp[amount]. The trace records [0, 7, 7, 7, 7, 7, 7], then amounts 1 through 6 becoming [0, 1, 2, 1, 1, 2, 2].
fmt.Println(dp[target]) prints 2; listString formats the full []int with fmt.Sprintf and strings.Join, printing [0, 1, 2, 1, 1, 2, 2].