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.

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

Scala DSA Implementation

basic.scala 
object Main extends App {
  def listString(values: Array[Int]): String = values.mkString("[", ", ", "]")
  val coins = Array(1, 3, 4)
  val target = 6
  val inf = target + 1
  val dp = Array.fill(target + 1)(inf)
  dp(0) = 0
  for (amount <- 1 to target) {
    for (coin <- coins) {
      if (amount >= coin) {
        val candidate = dp(amount - coin) + 1
        if (candidate < dp(amount)) dp(amount) = candidate
      }
    }
  }
  println(dp(target))
  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.

Initial DP table for target 6.a0a1a2a3a4a5a60777777

Step 2 - Early amounts become reachable

With coins 1, 3, and 4, amounts 1 through 4 fill as [1, 2, 1, 1].

Table after filling amounts 1 through 4.a0a1a2a3a4a5a60121177base11+134todotodo

Step 3 - Final answer at amount 6

dp[5] = 2 and dp[6] = 2, so the target needs two coins.

Final DP table: [0, 1, 2, 1, 1, 2, 2].a0a1a2a3a4a5a6012112211+1341+43+3

Implementation notes

  • coins is a Scala Array[Int] with values 1, 3, 4, and target is the fixed Int value 6.
  • val dp = Array.fill(target + 1)(inf) keeps the array reference fixed, while individual slots are still mutable.
  • The sentinel is inf = target + 1, so the initial table is [0, 7, 7, 7, 7, 7, 7] after dp(0) = 0.
  • The outer loop is amount-first: for (amount <- 1 to target), then for (coin <- coins) checks each coin for that amount.
  • if (amount >= coin) is the bounds guard before reading dp(amount - coin).
  • Each candidate is dp(amount - coin) + 1; the slot changes only when candidate < dp(amount).
  • The replay shows the table filling left to right: [0, 1, 2, 1, 1, 2, 2], with amount 6 ending at 2.
  • println(dp(target)) prints the answer first, then listString(dp) prints the full table with mkString("[", ", ", "]").

Output

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