1053 Intermediate

1053-coin-change — Coin Change

Functional Programming

Tutorial

The Problem

The coin change problem asks: given coin denominations and a target amount, what is the minimum number of coins to make that amount? This is a classic DP problem with applications in currency systems, memory allocators (minimal number of blocks to satisfy a request), and NP-hard scheduling approximations.

It is the canonical example of unbounded knapsack / complete knapsack: each coin can be used multiple times, and you want to minimize the count rather than maximize value.

🎯 Learning Outcomes

• Implement bottom-up DP for the coin change problem

• Understand the dp[i] = min(dp[i], dp[i-coin] + 1) recurrence

• Implement the same algorithm with top-down memoization

• Recognize the unbounded knapsack structure

• Handle the "no solution" case (return -1)

Code Example

#![allow(clippy::all)]
// 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
}

#[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"

Key Differences

Sentinel value: Both use amount + 1 as an infinity sentinel; Rust's explicit usize::MAX would overflow on addition.

Mutable array: OCaml's array is mutable by default; Rust's Vec<usize> requires no special annotation for mutation.

List vs slice iteration: OCaml iterates over coins with List.iter; Rust uses for &coin in coins.

Negative amounts: Rust's usize cannot represent negative values; the check if c <= i prevents underflow. OCaml's int allows subtraction without overflow.

OCaml Approach

let coin_change 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)

The OCaml version is structurally identical. Both use the same recurrence; the implementation differences are syntactic.

Full Source

#![allow(clippy::all)]
// 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
}

#[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"

✓ Tests Rust test suite

#[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);
    }
}

Deep 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)

Exercises

Extend to also reconstruct the actual coins used: return Vec<i32> of denominations that sum to the amount.

Implement a variant that counts the number of distinct ways to make the amount (combination sum count DP).

Solve the variant where each coin can only be used once (0/1 knapsack variant) and compare the recurrence change.

Open Source Repos

functional-rust

View the source for this example on GitHub — OCaml and Rust side by side in the repo.

Rust