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.

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 = "")

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