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.

Swift DSA Implementation

basic.swift 
func listString(_ values: [Int]) -> String {
    "[" + values.map(String.init).joined(separator: ", ") + "]"
}

let coins = [1, 3, 4]
let target = 6
let inf = target + 1
var dp = Array(repeating: inf, count: target + 1)
dp[0] = 0
for amount in 1...target {
    for coin in coins {
        if amount >= coin {
            let candidate = dp[amount - coin] + 1
            if candidate < dp[amount] {
                dp[amount] = candidate
            }
        }
    }
}
print(dp[target])
print(listString(dp))

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