1053: Coin Change

Difficulty: Intermediate Category: Dynamic Programming Concept: Find minimum number of coins to make a given amount — classic unbounded knapsack variant Key Insight: The DP recurrence `dp[i] = min(dp[i], dp[i-coin] + 1)` builds optimality bottom-up; BFS offers an alternative "shortest path" interpretation where each coin denomination is an edge.

// 1053: Coin Change — Minimum Coins for Amount

use std::collections::HashMap;

// Approach 1: Bottom-up DP
fn coin_change_dp(coins: &[i32], amount: i32) -> i32 {
    let amount = amount as usize;
    let max_val = amount + 1;
    let mut dp = vec![max_val; amount + 1];
    dp[0] = 0;
    for i in 1..=amount {
        for &coin in coins {
            let c = coin as usize;
            if c <= i && dp[i - c] + 1 < dp[i] {
                dp[i] = dp[i - c] + 1;
            }
        }
    }
    if dp[amount] > amount { -1 } else { dp[amount] as i32 }
}

// Approach 2: Recursive with HashMap memoization
fn coin_change_memo(coins: &[i32], amount: i32) -> i32 {
    fn solve(coins: &[i32], amt: i32, cache: &mut HashMap<i32, i32>) -> i32 {
        if amt == 0 { return 0; }
        if amt < 0 { return i32::MAX; }
        if let Some(&v) = cache.get(&amt) { return v; }
        let result = coins.iter().fold(i32::MAX, |best, &coin| {
            let sub = solve(coins, amt - coin, cache);
            if sub < i32::MAX { best.min(sub + 1) } else { best }
        });
        cache.insert(amt, result);
        result
    }
    let mut cache = HashMap::new();
    let r = solve(coins, amount, &mut cache);
    if r == i32::MAX { -1 } else { r }
}

// Approach 3: BFS (shortest path interpretation)
fn coin_change_bfs(coins: &[i32], amount: i32) -> i32 {
    if amount == 0 { return 0; }
    let mut visited = vec![false; amount as usize + 1];
    let mut queue = std::collections::VecDeque::new();
    queue.push_back((0i32, 0i32));
    visited[0] = true;
    while let Some((current, steps)) = queue.pop_front() {
        for &coin in coins {
            let next = current + coin;
            if next == amount { return steps + 1; }
            if next < amount && !visited[next as usize] {
                visited[next as usize] = true;
                queue.push_back((next, steps + 1));
            }
        }
    }
    -1
}

fn main() {
    println!("coins [1,5,10,25], amount 30 → {}", coin_change_dp(&[1, 5, 10, 25], 30));
    println!("coins [2], amount 3 → {}", coin_change_dp(&[2], 3));
    println!("coins [1,2,5], amount 11 → {}", coin_change_dp(&[1, 2, 5], 11));
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_coin_change_dp() {
        assert_eq!(coin_change_dp(&[1, 5, 10, 25], 30), 2);
        assert_eq!(coin_change_dp(&[1, 5, 10, 25], 11), 2);
        assert_eq!(coin_change_dp(&[2], 3), -1);
        assert_eq!(coin_change_dp(&[1], 0), 0);
        assert_eq!(coin_change_dp(&[1, 2, 5], 11), 3);
    }

    #[test]
    fn test_coin_change_memo() {
        assert_eq!(coin_change_memo(&[1, 5, 10, 25], 30), 2);
        assert_eq!(coin_change_memo(&[1, 5, 10, 25], 11), 2);
        assert_eq!(coin_change_memo(&[2], 3), -1);
        assert_eq!(coin_change_memo(&[1], 0), 0);
        assert_eq!(coin_change_memo(&[1, 2, 5], 11), 3);
    }

    #[test]
    fn test_coin_change_bfs() {
        assert_eq!(coin_change_bfs(&[1, 5, 10, 25], 30), 2);
        assert_eq!(coin_change_bfs(&[1, 5, 10, 25], 11), 2);
        assert_eq!(coin_change_bfs(&[2], 3), -1);
        assert_eq!(coin_change_bfs(&[1], 0), 0);
        assert_eq!(coin_change_bfs(&[1, 2, 5], 11), 3);
    }
}

(* 1053: Coin Change — Minimum Coins for Amount *)

(* Approach 1: Bottom-up DP *)
let coin_change_dp coins amount =
  let max_val = amount + 1 in
  let dp = Array.make (amount + 1) max_val in
  dp.(0) <- 0;
  for i = 1 to amount do
    List.iter (fun coin ->
      if coin <= i && dp.(i - coin) + 1 < dp.(i) then
        dp.(i) <- dp.(i - coin) + 1
    ) coins
  done;
  if dp.(amount) > amount then -1 else dp.(amount)

(* Approach 2: Recursive with memoization *)
let coin_change_memo coins amount =
  let cache = Hashtbl.create 128 in
  let rec solve amt =
    if amt = 0 then 0
    else if amt < 0 then max_int
    else
      match Hashtbl.find_opt cache amt with
      | Some v -> v
      | None ->
        let result = List.fold_left (fun best coin ->
          let sub = solve (amt - coin) in
          if sub < max_int then min best (sub + 1) else best
        ) max_int coins in
        Hashtbl.add cache amt result;
        result
  in
  let r = solve amount in
  if r = max_int then -1 else r

let () =
  (* Standard test cases *)
  assert (coin_change_dp [1; 5; 10; 25] 30 = 2);  (* 25 + 5 *)
  assert (coin_change_dp [1; 5; 10; 25] 11 = 2);  (* 10 + 1 *)
  assert (coin_change_dp [2] 3 = -1);               (* impossible *)
  assert (coin_change_dp [1] 0 = 0);                (* zero amount *)
  assert (coin_change_dp [1; 2; 5] 11 = 3);         (* 5 + 5 + 1 *)

  assert (coin_change_memo [1; 5; 10; 25] 30 = 2);
  assert (coin_change_memo [1; 5; 10; 25] 11 = 2);
  assert (coin_change_memo [2] 3 = -1);
  assert (coin_change_memo [1] 0 = 0);
  assert (coin_change_memo [1; 2; 5] 11 = 3);

  Printf.printf "✓ All tests passed\n"

📊 Detailed Comparison

Coin Change — Comparison

Core Insight

Coin change is the canonical unbounded knapsack problem. Bottom-up DP fills a 1D table; memoized recursion explores the same subproblems top-down. Both languages express the recurrence similarly, but Rust adds a BFS approach treating it as a shortest-path problem.

OCaml Approach

Imperative array DP with nested `List.iter` for coins
Memoized recursion using `Hashtbl` and `List.fold_left` for clean min-finding
Pattern matching on `find_opt` for cache lookup

Rust Approach

`vec!` DP table with nested iteration — straightforward translation
`HashMap` memoization with inner function taking `&mut` cache
`VecDeque` BFS approach — coins as graph edges, amount as target node
`i32::MAX` as sentinel vs OCaml's `max_int`

Comparison Table

Aspect	OCaml	Rust
DP table	`Array.make (n+1) max_val`	`vec![max_val; n + 1]`
Impossible sentinel	`max_int`	`i32::MAX`
Coin iteration	`List.iter`	`for &coin in coins`
Min finding	`List.fold_left` with `min`	`.iter().fold()` with `.min()`
BFS approach	Not shown (less idiomatic)	`VecDeque` — natural in Rust
Return convention	`-1` for impossible	`-1` for impossible (LeetCode style)