1073 Advanced

1073-burst-balloons — Burst Balloons

Functional Programming

Tutorial

The Problem

The burst balloons problem is an interval DP gem: given a row of balloons with numbers, bursting balloon k earns nums[k-1] * nums[k] * nums[k+1] coins. Find the maximum coins from bursting all balloons in the best order. The key insight is reasoning about the LAST balloon to burst in an interval, not the first.

This "think backwards" trick converts an exponential search into a polynomial DP, and the same pattern appears in matrix chain multiplication, optimal binary search trees, and stone merging problems.

🎯 Learning Outcomes

• Understand interval DP and the "last element" thinking strategy

• Implement burst balloons with dp[i][j] = max coins for interval (i, j) exclusive

• Add sentinel values (1, ...nums..., 1) to handle edge balloons cleanly

• Compare top-down memoization to bottom-up interval DP

• Apply the "think backwards" strategy to other interval DP problems

Code Example

#![allow(clippy::all)]
// 1073: Burst Balloons — Interval DP

use std::collections::HashMap;

// Approach 1: Bottom-up interval DP
fn max_coins_dp(nums: &[i32]) -> i32 {
    let n = nums.len();
    let mut balloons = vec![1i32; n + 2];
    for i in 0..n {
        balloons[i + 1] = nums[i];
    }
    let len = n + 2;
    let mut dp = vec![vec![0i32; len]; len];

    for gap in 2..len {
        for i in 0..len - gap {
            let j = i + gap;
            for k in (i + 1)..j {
                let coins = dp[i][k] + dp[k][j] + balloons[i] * balloons[k] * balloons[j];
                dp[i][j] = dp[i][j].max(coins);
            }
        }
    }
    dp[0][len - 1]
}

// Approach 2: Recursive with memoization
fn max_coins_memo(nums: &[i32]) -> i32 {
    let n = nums.len();
    let mut balloons = vec![1i32; n + 2];
    for i in 0..n {
        balloons[i + 1] = nums[i];
    }
    let len = n + 2;

    fn solve(
        left: usize,
        right: usize,
        balloons: &[i32],
        cache: &mut HashMap<(usize, usize), i32>,
    ) -> i32 {
        if right.saturating_sub(left) < 2 {
            return 0;
        }
        if let Some(&v) = cache.get(&(left, right)) {
            return v;
        }
        let mut best = 0;
        for k in (left + 1)..right {
            let coins = solve(left, k, balloons, cache)
                + solve(k, right, balloons, cache)
                + balloons[left] * balloons[k] * balloons[right];
            best = best.max(coins);
        }
        cache.insert((left, right), best);
        best
    }

    let mut cache = HashMap::new();
    solve(0, len - 1, &balloons, &mut cache)
}

// Approach 3: Divide and conquer (same logic, different framing)
fn max_coins_dc(nums: &[i32]) -> i32 {
    let n = nums.len();
    let mut balloons = vec![1i32; n + 2];
    for i in 0..n {
        balloons[i + 1] = nums[i];
    }
    let len = n + 2;
    let mut memo = vec![vec![-1i32; len]; len];

    fn solve(l: usize, r: usize, balloons: &[i32], memo: &mut Vec<Vec<i32>>) -> i32 {
        if r.saturating_sub(l) < 2 {
            return 0;
        }
        if memo[l][r] >= 0 {
            return memo[l][r];
        }
        let mut best = 0;
        for k in (l + 1)..r {
            let coins = solve(l, k, balloons, memo)
                + solve(k, r, balloons, memo)
                + balloons[l] * balloons[k] * balloons[r];
            best = best.max(coins);
        }
        memo[l][r] = best;
        best
    }

    solve(0, len - 1, &balloons, &mut memo)
}

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

    #[test]
    fn test_dp() {
        assert_eq!(max_coins_dp(&[3, 1, 5, 8]), 167);
        assert_eq!(max_coins_dp(&[1, 5]), 10);
        assert_eq!(max_coins_dp(&[1]), 1);
    }

    #[test]
    fn test_memo() {
        assert_eq!(max_coins_memo(&[3, 1, 5, 8]), 167);
        assert_eq!(max_coins_memo(&[1, 5]), 10);
    }

    #[test]
    fn test_dc() {
        assert_eq!(max_coins_dc(&[3, 1, 5, 8]), 167);
        assert_eq!(max_coins_dc(&[1, 5]), 10);
    }
}

(* 1073: Burst Balloons — Interval DP *)

(* Approach 1: Bottom-up interval DP *)
let max_coins_dp nums =
  (* Add virtual balloons with value 1 at both ends *)
  let n = Array.length nums in
  let balloons = Array.init (n + 2) (fun i ->
    if i = 0 || i = n + 1 then 1 else nums.(i - 1)
  ) in
  let len = n + 2 in
  let dp = Array.init len (fun _ -> Array.make len 0) in
  (* dp.(i).(j) = max coins from bursting all balloons between i and j (exclusive) *)
  for gap = 2 to len - 1 do
    for i = 0 to len - gap - 1 do
      let j = i + gap in
      for k = i + 1 to j - 1 do
        let coins = dp.(i).(k) + dp.(k).(j)
                    + balloons.(i) * balloons.(k) * balloons.(j) in
        dp.(i).(j) <- max dp.(i).(j) coins
      done
    done
  done;
  dp.(0).(len - 1)

(* Approach 2: Recursive with memoization *)
let max_coins_memo nums =
  let n = Array.length nums in
  let balloons = Array.init (n + 2) (fun i ->
    if i = 0 || i = n + 1 then 1 else nums.(i - 1)
  ) in
  let len = n + 2 in
  let cache = Hashtbl.create 64 in
  let rec solve left right =
    if right - left < 2 then 0
    else
      match Hashtbl.find_opt cache (left, right) with
      | Some v -> v
      | None ->
        let best = ref 0 in
        for k = left + 1 to right - 1 do
          let coins = solve left k + solve k right
                      + balloons.(left) * balloons.(k) * balloons.(right) in
          best := max !best coins
        done;
        Hashtbl.add cache (left, right) !best;
        !best
  in
  solve 0 (len - 1)

let () =
  assert (max_coins_dp [|3; 1; 5; 8|] = 167);
  assert (max_coins_dp [|1; 5|] = 10);
  assert (max_coins_dp [|1|] = 1);

  assert (max_coins_memo [|3; 1; 5; 8|] = 167);
  assert (max_coins_memo [|1; 5|] = 10);

  Printf.printf "✓ All tests passed\n"

Key Differences

Sentinel insertion: Both prepend and append 1 to handle boundary conditions; Rust uses vec![1; n+2] with array blit, OCaml uses Array.make.

Interval filling order: Both fill by increasing gap size — a fundamental constraint of interval DP ensuring sub-intervals are computed before larger ones.

**usize::MAX risk**: Rust must avoid usize::MAX initialization for max-problems; using 0 and taking max works here since coins are non-negative.

"Think backwards" applicability: Same pattern applies to matrix chain (1057), stone merge, and optimal BST — recognizing the pattern is the key skill.

OCaml Approach

let max_coins nums =
  let n = Array.length nums in
  let b = Array.make (n+2) 1 in
  Array.blit nums 0 b 1 n;
  let len = n + 2 in
  let dp = Array.make_matrix len len 0 in
  for gap = 2 to len - 1 do
    for i = 0 to len - gap - 1 do
      let j = i + gap in
      for k = i + 1 to j - 1 do
        let coins = dp.(i).(k) + dp.(k).(j) + b.(i) * b.(k) * b.(j) in
        if coins > dp.(i).(j) then dp.(i).(j) <- coins
      done
    done
  done;
  dp.(0).(len-1)

Structurally identical. The sentinel-insertion and interval-filling logic is purely mathematical.

Full Source

#![allow(clippy::all)]
// 1073: Burst Balloons — Interval DP

use std::collections::HashMap;

// Approach 1: Bottom-up interval DP
fn max_coins_dp(nums: &[i32]) -> i32 {
    let n = nums.len();
    let mut balloons = vec![1i32; n + 2];
    for i in 0..n {
        balloons[i + 1] = nums[i];
    }
    let len = n + 2;
    let mut dp = vec![vec![0i32; len]; len];

    for gap in 2..len {
        for i in 0..len - gap {
            let j = i + gap;
            for k in (i + 1)..j {
                let coins = dp[i][k] + dp[k][j] + balloons[i] * balloons[k] * balloons[j];
                dp[i][j] = dp[i][j].max(coins);
            }
        }
    }
    dp[0][len - 1]
}

// Approach 2: Recursive with memoization
fn max_coins_memo(nums: &[i32]) -> i32 {
    let n = nums.len();
    let mut balloons = vec![1i32; n + 2];
    for i in 0..n {
        balloons[i + 1] = nums[i];
    }
    let len = n + 2;

    fn solve(
        left: usize,
        right: usize,
        balloons: &[i32],
        cache: &mut HashMap<(usize, usize), i32>,
    ) -> i32 {
        if right.saturating_sub(left) < 2 {
            return 0;
        }
        if let Some(&v) = cache.get(&(left, right)) {
            return v;
        }
        let mut best = 0;
        for k in (left + 1)..right {
            let coins = solve(left, k, balloons, cache)
                + solve(k, right, balloons, cache)
                + balloons[left] * balloons[k] * balloons[right];
            best = best.max(coins);
        }
        cache.insert((left, right), best);
        best
    }

    let mut cache = HashMap::new();
    solve(0, len - 1, &balloons, &mut cache)
}

// Approach 3: Divide and conquer (same logic, different framing)
fn max_coins_dc(nums: &[i32]) -> i32 {
    let n = nums.len();
    let mut balloons = vec![1i32; n + 2];
    for i in 0..n {
        balloons[i + 1] = nums[i];
    }
    let len = n + 2;
    let mut memo = vec![vec![-1i32; len]; len];

    fn solve(l: usize, r: usize, balloons: &[i32], memo: &mut Vec<Vec<i32>>) -> i32 {
        if r.saturating_sub(l) < 2 {
            return 0;
        }
        if memo[l][r] >= 0 {
            return memo[l][r];
        }
        let mut best = 0;
        for k in (l + 1)..r {
            let coins = solve(l, k, balloons, memo)
                + solve(k, r, balloons, memo)
                + balloons[l] * balloons[k] * balloons[r];
            best = best.max(coins);
        }
        memo[l][r] = best;
        best
    }

    solve(0, len - 1, &balloons, &mut memo)
}

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

    #[test]
    fn test_dp() {
        assert_eq!(max_coins_dp(&[3, 1, 5, 8]), 167);
        assert_eq!(max_coins_dp(&[1, 5]), 10);
        assert_eq!(max_coins_dp(&[1]), 1);
    }

    #[test]
    fn test_memo() {
        assert_eq!(max_coins_memo(&[3, 1, 5, 8]), 167);
        assert_eq!(max_coins_memo(&[1, 5]), 10);
    }

    #[test]
    fn test_dc() {
        assert_eq!(max_coins_dc(&[3, 1, 5, 8]), 167);
        assert_eq!(max_coins_dc(&[1, 5]), 10);
    }
}

(* 1073: Burst Balloons — Interval DP *)

(* Approach 1: Bottom-up interval DP *)
let max_coins_dp nums =
  (* Add virtual balloons with value 1 at both ends *)
  let n = Array.length nums in
  let balloons = Array.init (n + 2) (fun i ->
    if i = 0 || i = n + 1 then 1 else nums.(i - 1)
  ) in
  let len = n + 2 in
  let dp = Array.init len (fun _ -> Array.make len 0) in
  (* dp.(i).(j) = max coins from bursting all balloons between i and j (exclusive) *)
  for gap = 2 to len - 1 do
    for i = 0 to len - gap - 1 do
      let j = i + gap in
      for k = i + 1 to j - 1 do
        let coins = dp.(i).(k) + dp.(k).(j)
                    + balloons.(i) * balloons.(k) * balloons.(j) in
        dp.(i).(j) <- max dp.(i).(j) coins
      done
    done
  done;
  dp.(0).(len - 1)

(* Approach 2: Recursive with memoization *)
let max_coins_memo nums =
  let n = Array.length nums in
  let balloons = Array.init (n + 2) (fun i ->
    if i = 0 || i = n + 1 then 1 else nums.(i - 1)
  ) in
  let len = n + 2 in
  let cache = Hashtbl.create 64 in
  let rec solve left right =
    if right - left < 2 then 0
    else
      match Hashtbl.find_opt cache (left, right) with
      | Some v -> v
      | None ->
        let best = ref 0 in
        for k = left + 1 to right - 1 do
          let coins = solve left k + solve k right
                      + balloons.(left) * balloons.(k) * balloons.(right) in
          best := max !best coins
        done;
        Hashtbl.add cache (left, right) !best;
        !best
  in
  solve 0 (len - 1)

let () =
  assert (max_coins_dp [|3; 1; 5; 8|] = 167);
  assert (max_coins_dp [|1; 5|] = 10);
  assert (max_coins_dp [|1|] = 1);

  assert (max_coins_memo [|3; 1; 5; 8|] = 167);
  assert (max_coins_memo [|1; 5|] = 10);

  Printf.printf "✓ All tests passed\n"

✓ Tests Rust test suite

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

    #[test]
    fn test_dp() {
        assert_eq!(max_coins_dp(&[3, 1, 5, 8]), 167);
        assert_eq!(max_coins_dp(&[1, 5]), 10);
        assert_eq!(max_coins_dp(&[1]), 1);
    }

    #[test]
    fn test_memo() {
        assert_eq!(max_coins_memo(&[3, 1, 5, 8]), 167);
        assert_eq!(max_coins_memo(&[1, 5]), 10);
    }

    #[test]
    fn test_dc() {
        assert_eq!(max_coins_dc(&[3, 1, 5, 8]), 167);
        assert_eq!(max_coins_dc(&[1, 5]), 10);
    }
}

Deep Comparison

Burst Balloons — Comparison

Core Insight

Burst balloons is interval DP: think about which balloon to burst last in each subinterval. Adding virtual boundary balloons (value 1) simplifies edge cases. dp[i][j] = max coins obtainable from all balloons strictly between i and j.

OCaml Approach

• Array.init (n+2) for padded balloon array

• Triple-nested loops for gap/start/split

• max for tracking best split

• Hashtbl with tuple keys for memoization

Rust Approach

• vec![1i32; n+2] for padded array

• Same triple-nested loop structure

• .max() chained method

• Two memoization styles: HashMap and 2D Vec<Vec<i32>> with -1 sentinel

Comparison Table

Aspect	OCaml	Rust
Padded array	`Array.init (n+2) (fun i -> ...)`	`vec![1; n+2]` + fill loop
Memo sentinel	`Hashtbl` (no sentinel needed)	`vec![vec![-1; len]; len]` or `HashMap`
Gap iteration	`for gap = 2 to len-1`	`for gap in 2..len`
Overflow risk	OCaml ints (63-bit)	`i32` — safe for typical inputs

Exercises

Reconstruct the optimal burst order using a separate order table that records the chosen k at each dp[i][j].

Solve the stone merging problem using the same interval DP pattern: merge adjacent stones, cost = sum of merged stones.

Implement the "stone game" variant where two players alternate bursting balloons and both want to maximize their own coins.

Open Source Repos

functional-rust

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

Rust