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.

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

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