788 Intermediate

788-coin-change-dp — Coin Change

Functional Programming

Tutorial Video

Text description (accessibility)

This video demonstrates the "788-coin-change-dp — Coin Change" functional Rust example. Difficulty level: Intermediate. Key concepts covered: Functional Programming. The coin change problem asks: given denominations of coins and an amount, what is the minimum number of coins needed to make that amount? Key difference from OCaml: 1. **Sentinel value**: Rust uses `usize::MAX` as "impossible"; OCaml uses `max_int` — same concept, different constant name.

Tutorial

The Problem

The coin change problem asks: given denominations of coins and an amount, what is the minimum number of coins needed to make that amount? Greedy fails for non-standard denominations (e.g., coins of 1, 3, 4 — greedy gives 3 coins for 6, but optimal is 2). DP finds the true minimum. The counting variant (number of ways to make change) is used in combinatorics and financial applications. Canonical in algorithm courses since the 1970s.

🎯 Learning Outcomes

• Implement coin_change(coins, amount) -> Option<usize> returning None when impossible

• Use the bottom-up recurrence: dp[i] = min over coins c: dp[i-c] + 1

• Distinguish the minimum-count problem from the counting-ways problem (coin_change_ways)

• Understand why the top-down memoized approach is equivalent but sometimes cleaner

• Reconstruct the actual coins chosen, not just the count

Code Example

#![allow(clippy::all)]
//! # Coin Change

pub fn coin_change(coins: &[usize], amount: usize) -> Option<usize> {
    let mut dp = vec![usize::MAX; amount + 1];
    dp[0] = 0;
    for i in 1..=amount {
        for &coin in coins {
            if coin <= i && dp[i - coin] != usize::MAX {
                dp[i] = dp[i].min(dp[i - coin] + 1);
            }
        }
    }
    if dp[amount] == usize::MAX {
        None
    } else {
        Some(dp[amount])
    }
}

pub fn coin_change_ways(coins: &[usize], amount: usize) -> usize {
    let mut dp = vec![0usize; amount + 1];
    dp[0] = 1;
    for &coin in coins {
        for i in coin..=amount {
            dp[i] += dp[i - coin];
        }
    }
    dp[amount]
}

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

    #[test]
    fn test_change() {
        assert_eq!(coin_change(&[1, 2, 5], 11), Some(3));
    }
    #[test]
    fn test_ways() {
        assert_eq!(coin_change_ways(&[1, 2, 5], 5), 4);
    }
    #[test]
    fn test_impossible() {
        assert_eq!(coin_change(&[2], 3), None);
    }
}

(* Coin change: minimum coins in OCaml *)

(* ── Recursive with memoisation (top-down) ──────────────────────────────────── *)
let coin_change_memo coins amount =
  let memo = Hashtbl.create 128 in
  let rec dp n =
    if n = 0 then Some 0
    else if n < 0 then None
    else match Hashtbl.find_opt memo n with
    | Some v -> v
    | None ->
      let best =
        List.fold_left (fun best coin ->
          match dp (n - coin) with
          | None -> best
          | Some sub ->
            match best with
            | None -> Some (1 + sub)
            | Some b -> Some (min b (1 + sub))
        ) None coins
      in
      Hashtbl.replace memo n best;
      best
  in
  dp amount

(* ── Tabulation (bottom-up) ────────────────────────────────────────────────────── *)
let coin_change_tab coins amount =
  let dp = Array.make (amount + 1) (amount + 1) in (* sentinel = amount+1 *)
  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 None else Some dp.(amount)

(* ── Count ways ─────────────────────────────────────────────────────────────── *)
let count_ways coins amount =
  let dp = Array.make (amount + 1) 0 in
  dp.(0) <- 1;
  List.iter (fun coin ->
    for i = coin to amount do
      dp.(i) <- dp.(i) + dp.(i - coin)
    done
  ) coins;
  dp.(amount)

let () =
  let coins = [1; 5; 10; 25] in
  let amounts = [0; 11; 30; 41; 100] in
  List.iter (fun amt ->
    let m = coin_change_memo coins amt in
    let t = coin_change_tab  coins amt in
    let w = count_ways coins amt in
    Printf.printf "amount=%3d: min_coins=%s  ways=%d\n"
      amt
      (match m with Some n -> string_of_int n | None -> "none")
      w;
    assert (m = t)  (* both methods agree *)
  ) amounts

Key Differences

Sentinel value: Rust uses usize::MAX as "impossible"; OCaml uses max_int — same concept, different constant name.

Overflow guard: Rust's usize::MAX + 1 would panic; the != usize::MAX guard prevents this; OCaml has the same issue with max_int + 1.

Return type: Rust's Option<usize> clearly communicates impossibility; OCaml might return -1 or Int.max_int without a dedicated option type.

Counting variant: coin_change_ways uses a different loop structure (iterate coins in outer loop for combinations); both languages implement it identically.

OCaml Approach

OCaml implements the same bottom-up DP with Array.make (amount+1) max_int and a nested for loop. Functional style uses List.fold_left over coins. The Int.max_int sentinel instead of usize::MAX. Reconstruction uses a prev: int array tracking which coin was used at each step. OCaml's min_coins function in competitive programming is often a one-liner using Array.fold_left.

Full Source

#![allow(clippy::all)]
//! # Coin Change

pub fn coin_change(coins: &[usize], amount: usize) -> Option<usize> {
    let mut dp = vec![usize::MAX; amount + 1];
    dp[0] = 0;
    for i in 1..=amount {
        for &coin in coins {
            if coin <= i && dp[i - coin] != usize::MAX {
                dp[i] = dp[i].min(dp[i - coin] + 1);
            }
        }
    }
    if dp[amount] == usize::MAX {
        None
    } else {
        Some(dp[amount])
    }
}

pub fn coin_change_ways(coins: &[usize], amount: usize) -> usize {
    let mut dp = vec![0usize; amount + 1];
    dp[0] = 1;
    for &coin in coins {
        for i in coin..=amount {
            dp[i] += dp[i - coin];
        }
    }
    dp[amount]
}

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

    #[test]
    fn test_change() {
        assert_eq!(coin_change(&[1, 2, 5], 11), Some(3));
    }
    #[test]
    fn test_ways() {
        assert_eq!(coin_change_ways(&[1, 2, 5], 5), 4);
    }
    #[test]
    fn test_impossible() {
        assert_eq!(coin_change(&[2], 3), None);
    }
}

(* Coin change: minimum coins in OCaml *)

(* ── Recursive with memoisation (top-down) ──────────────────────────────────── *)
let coin_change_memo coins amount =
  let memo = Hashtbl.create 128 in
  let rec dp n =
    if n = 0 then Some 0
    else if n < 0 then None
    else match Hashtbl.find_opt memo n with
    | Some v -> v
    | None ->
      let best =
        List.fold_left (fun best coin ->
          match dp (n - coin) with
          | None -> best
          | Some sub ->
            match best with
            | None -> Some (1 + sub)
            | Some b -> Some (min b (1 + sub))
        ) None coins
      in
      Hashtbl.replace memo n best;
      best
  in
  dp amount

(* ── Tabulation (bottom-up) ────────────────────────────────────────────────────── *)
let coin_change_tab coins amount =
  let dp = Array.make (amount + 1) (amount + 1) in (* sentinel = amount+1 *)
  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 None else Some dp.(amount)

(* ── Count ways ─────────────────────────────────────────────────────────────── *)
let count_ways coins amount =
  let dp = Array.make (amount + 1) 0 in
  dp.(0) <- 1;
  List.iter (fun coin ->
    for i = coin to amount do
      dp.(i) <- dp.(i) + dp.(i - coin)
    done
  ) coins;
  dp.(amount)

let () =
  let coins = [1; 5; 10; 25] in
  let amounts = [0; 11; 30; 41; 100] in
  List.iter (fun amt ->
    let m = coin_change_memo coins amt in
    let t = coin_change_tab  coins amt in
    let w = count_ways coins amt in
    Printf.printf "amount=%3d: min_coins=%s  ways=%d\n"
      amt
      (match m with Some n -> string_of_int n | None -> "none")
      w;
    assert (m = t)  (* both methods agree *)
  ) amounts

✓ Tests Rust test suite

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

    #[test]
    fn test_change() {
        assert_eq!(coin_change(&[1, 2, 5], 11), Some(3));
    }
    #[test]
    fn test_ways() {
        assert_eq!(coin_change_ways(&[1, 2, 5], 5), 4);
    }
    #[test]
    fn test_impossible() {
        assert_eq!(coin_change(&[2], 3), None);
    }
}

Deep Comparison

OCaml vs Rust: Coin Change Dp

Overview

See the example.rs and example.ml files for detailed implementations.

Key Differences

Aspect	OCaml	Rust
Type system	Hindley-Milner	Ownership + traits
Memory	GC	Zero-cost abstractions
Mutability	Explicit ref	mut keyword
Error handling	Option/Result	Result<T, E>

See README.md for detailed comparison.

Exercises

Implement coin_change_reconstruct(coins, amount) -> Option<Vec<usize>> that returns the actual coins used, not just the count.

Add coin_change_limited(coins, counts, amount) where counts[i] limits how many times coin i can be used (bounded knapsack variant).

Implement the top-down memoized version and benchmark it against the bottom-up version for large amounts (100,000+). Which is faster in practice?

Open Source Repos

functional-rust

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

Rust