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

R DSA Implementation

basic.R 
list_string <- function(values) paste0("[", paste(values, collapse = ", "), "]")
coins <- c(1, 3, 4)
target <- 6
inf <- target + 1
dp <- rep(inf, target + 1)
dp[1] <- 0
for (amount in 1:target) {
  for (coin in coins) {
    if (amount >= coin) {
      candidate <- dp[amount - coin + 1] + 1
      if (candidate < dp[amount + 1]) dp[amount + 1] <- candidate
    }
  }
}
cat(dp[target + 1], "\n", sep = "")
cat(list_string(dp), "\n", sep = "")

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 <- c(1, 3, 4), target <- 6, and inf <- target + 1 set the pinned data. Here the sentinel is 7.
  • dp <- rep(inf, target + 1) creates seven R vector entries for logical amounts 0 through 6.
  • Because R vectors are 1-based, amount 0 lives at dp[1]. dp[1] <- 0 makes the initial table [0, 7, 7, 7, 7, 7, 7].
  • for (amount in 1:target) scans amounts 1 through 6; the inner for (coin in coins) tries coins 1, 3, and 4.
  • if (amount >= coin) guards the read so the code only looks back to valid smaller amounts.
  • candidate <- dp[amount - coin + 1] + 1 uses + 1 to translate a logical amount into the R vector index.
  • if (candidate < dp[amount + 1]) dp[amount + 1] <- candidate writes the best value found for that amount.

Replay steps

init: [0, 7, 7, 7, 7, 7, 7]
a=1:  [0, 1, 7, 7, 7, 7, 7]
a=2:  [0, 1, 2, 7, 7, 7, 7]
a=3:  [0, 1, 2, 1, 7, 7, 7]
a=4:  [0, 1, 2, 1, 1, 7, 7]
a=5:  [0, 1, 2, 1, 1, 2, 7]
a=6:  [0, 1, 2, 1, 1, 2, 2]
  • The answer is read from dp[target + 1], so dp[7] is 2 for amount 6.
  • list_string(dp) formats the full table, and the two cat(...) calls print the answer and table exactly as shown below.

Output

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