1059 Advanced

1059-rod-cutting — Rod Cutting

Functional Programming

Tutorial

The Problem

Rod cutting asks: given a rod of length n and a price table for each possible length, how should you cut the rod to maximize revenue? Cutting a rod of length 7 into pieces of length 3 and 4 might be worth more than selling it whole. This is an unbounded knapsack variant where the rod lengths are the "item sizes" and prices are the "values."

The problem appears in metal fabrication, lumber pricing, fiber optic cable installation, and any scenario where raw material can be sold at different rates by size.

🎯 Learning Outcomes

• Implement rod cutting using bottom-up DP

• Understand the unbounded knapsack structure (each piece can be cut repeatedly)

• Implement the memoized top-down variant

• Reconstruct the optimal cut sequence

• Recognize the difference from 0/1 knapsack (unbounded reuse)

Code Example

#![allow(clippy::all)]
// 1059: Rod Cutting — Maximize Revenue

use std::collections::HashMap;

// Approach 1: Bottom-up DP
fn rod_cut_dp(prices: &[i64], n: usize) -> i64 {
    let mut dp = vec![0i64; n + 1];
    for i in 1..=n {
        for j in 1..=i.min(prices.len()) {
            dp[i] = dp[i].max(prices[j - 1] + dp[i - j]);
        }
    }
    dp[n]
}

// Approach 2: Top-down with memoization
fn rod_cut_memo(prices: &[i64], n: usize) -> i64 {
    fn solve(len: usize, prices: &[i64], cache: &mut HashMap<usize, i64>) -> i64 {
        if len == 0 {
            return 0;
        }
        if let Some(&v) = cache.get(&len) {
            return v;
        }
        let mut best = 0;
        for j in 1..=len.min(prices.len()) {
            best = best.max(prices[j - 1] + solve(len - j, prices, cache));
        }
        cache.insert(len, best);
        best
    }
    let mut cache = HashMap::new();
    solve(n, prices, &mut cache)
}

// Approach 3: With cut reconstruction
fn rod_cut_with_cuts(prices: &[i64], n: usize) -> (i64, Vec<usize>) {
    let mut dp = vec![0i64; n + 1];
    let mut cuts = vec![0usize; n + 1];
    for i in 1..=n {
        for j in 1..=i.min(prices.len()) {
            let val = prices[j - 1] + dp[i - j];
            if val > dp[i] {
                dp[i] = val;
                cuts[i] = j;
            }
        }
    }
    let mut result = Vec::new();
    let mut remaining = n;
    while remaining > 0 {
        result.push(cuts[remaining]);
        remaining -= cuts[remaining];
    }
    (dp[n], result)
}

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

    #[test]
    fn test_rod_cut_dp() {
        assert_eq!(rod_cut_dp(&[1, 5, 8, 9, 10, 17, 17, 20], 8), 22);
        assert_eq!(rod_cut_dp(&[1, 5, 8, 9, 10, 17, 17, 20], 4), 10);
        assert_eq!(rod_cut_dp(&[3, 5, 8, 9, 10, 17, 17, 20], 4), 12);
    }

    #[test]
    fn test_rod_cut_memo() {
        assert_eq!(rod_cut_memo(&[1, 5, 8, 9, 10, 17, 17, 20], 8), 22);
        assert_eq!(rod_cut_memo(&[1, 5, 8, 9, 10, 17, 17, 20], 4), 10);
    }

    #[test]
    fn test_rod_cut_with_cuts() {
        let (revenue, cuts) = rod_cut_with_cuts(&[1, 5, 8, 9, 10, 17, 17, 20], 8);
        assert_eq!(revenue, 22);
        assert_eq!(cuts.iter().sum::<usize>(), 8);
    }
}

(* 1059: Rod Cutting — Maximize Revenue *)

(* Approach 1: Bottom-up DP *)
let rod_cut_dp prices n =
  let dp = Array.make (n + 1) 0 in
  for i = 1 to n do
    for j = 1 to i do
      if j <= Array.length prices then
        dp.(i) <- max dp.(i) (prices.(j - 1) + dp.(i - j))
    done
  done;
  dp.(n)

(* Approach 2: Top-down with memoization *)
let rod_cut_memo prices n =
  let cache = Hashtbl.create 32 in
  let rec solve len =
    if len = 0 then 0
    else
      match Hashtbl.find_opt cache len with
      | Some v -> v
      | None ->
        let best = ref 0 in
        for j = 1 to min len (Array.length prices) do
          best := max !best (prices.(j - 1) + solve (len - j))
        done;
        Hashtbl.add cache len !best;
        !best
  in
  solve n

(* Approach 3: With cut reconstruction *)
let rod_cut_with_cuts prices n =
  let dp = Array.make (n + 1) 0 in
  let cuts = Array.make (n + 1) 0 in
  for i = 1 to n do
    for j = 1 to min i (Array.length prices) do
      let val_ = prices.(j - 1) + dp.(i - j) in
      if val_ > dp.(i) then begin
        dp.(i) <- val_;
        cuts.(i) <- j
      end
    done
  done;
  (* Reconstruct cuts *)
  let result = ref [] in
  let remaining = ref n in
  while !remaining > 0 do
    result := cuts.(!remaining) :: !result;
    remaining := !remaining - cuts.(!remaining)
  done;
  (dp.(n), List.rev !result)

let () =
  let prices = [|1; 5; 8; 9; 10; 17; 17; 20|] in
  assert (rod_cut_dp prices 8 = 22);
  assert (rod_cut_dp prices 4 = 10);
  assert (rod_cut_memo prices 8 = 22);
  assert (rod_cut_memo prices 4 = 10);
  let (revenue, _cuts) = rod_cut_with_cuts prices 8 in
  assert (revenue = 22);

  let prices2 = [|3; 5; 8; 9; 10; 17; 17; 20|] in
  assert (rod_cut_dp prices2 4 = 12);

  Printf.printf "✓ All tests passed\n"

Key Differences

**prices.len() vs Array.length prices**: Rust's prices.len() and OCaml's Array.length prices are equivalent but syntactically different.

1-indexed prices: Both use prices[j-1] for a 0-indexed array accessed with 1-based cut length; the off-by-one is a direct consequence of the domain (length 1 cut costs prices[0]).

Reconstruction: Both use a cuts array recording the optimal first cut, then loop to peel off the cuts one by one.

CLRS connection: This is CLRS Chapter 15's first DP example — the algorithms textbook formulation matches both implementations exactly.

OCaml Approach

let rod_cut prices n =
  let dp = Array.make (n + 1) 0 in
  for i = 1 to n do
    for j = 1 to min i (Array.length prices) do
      dp.(i) <- max dp.(i) (prices.(j-1) + dp.(i - j))
    done
  done;
  dp.(n)

Identical structure to Rust. Both iterate over rod lengths in the outer loop and cut sizes in the inner loop, taking the maximum revenue at each step.

Full Source

#![allow(clippy::all)]
// 1059: Rod Cutting — Maximize Revenue

use std::collections::HashMap;

// Approach 1: Bottom-up DP
fn rod_cut_dp(prices: &[i64], n: usize) -> i64 {
    let mut dp = vec![0i64; n + 1];
    for i in 1..=n {
        for j in 1..=i.min(prices.len()) {
            dp[i] = dp[i].max(prices[j - 1] + dp[i - j]);
        }
    }
    dp[n]
}

// Approach 2: Top-down with memoization
fn rod_cut_memo(prices: &[i64], n: usize) -> i64 {
    fn solve(len: usize, prices: &[i64], cache: &mut HashMap<usize, i64>) -> i64 {
        if len == 0 {
            return 0;
        }
        if let Some(&v) = cache.get(&len) {
            return v;
        }
        let mut best = 0;
        for j in 1..=len.min(prices.len()) {
            best = best.max(prices[j - 1] + solve(len - j, prices, cache));
        }
        cache.insert(len, best);
        best
    }
    let mut cache = HashMap::new();
    solve(n, prices, &mut cache)
}

// Approach 3: With cut reconstruction
fn rod_cut_with_cuts(prices: &[i64], n: usize) -> (i64, Vec<usize>) {
    let mut dp = vec![0i64; n + 1];
    let mut cuts = vec![0usize; n + 1];
    for i in 1..=n {
        for j in 1..=i.min(prices.len()) {
            let val = prices[j - 1] + dp[i - j];
            if val > dp[i] {
                dp[i] = val;
                cuts[i] = j;
            }
        }
    }
    let mut result = Vec::new();
    let mut remaining = n;
    while remaining > 0 {
        result.push(cuts[remaining]);
        remaining -= cuts[remaining];
    }
    (dp[n], result)
}

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

    #[test]
    fn test_rod_cut_dp() {
        assert_eq!(rod_cut_dp(&[1, 5, 8, 9, 10, 17, 17, 20], 8), 22);
        assert_eq!(rod_cut_dp(&[1, 5, 8, 9, 10, 17, 17, 20], 4), 10);
        assert_eq!(rod_cut_dp(&[3, 5, 8, 9, 10, 17, 17, 20], 4), 12);
    }

    #[test]
    fn test_rod_cut_memo() {
        assert_eq!(rod_cut_memo(&[1, 5, 8, 9, 10, 17, 17, 20], 8), 22);
        assert_eq!(rod_cut_memo(&[1, 5, 8, 9, 10, 17, 17, 20], 4), 10);
    }

    #[test]
    fn test_rod_cut_with_cuts() {
        let (revenue, cuts) = rod_cut_with_cuts(&[1, 5, 8, 9, 10, 17, 17, 20], 8);
        assert_eq!(revenue, 22);
        assert_eq!(cuts.iter().sum::<usize>(), 8);
    }
}

(* 1059: Rod Cutting — Maximize Revenue *)

(* Approach 1: Bottom-up DP *)
let rod_cut_dp prices n =
  let dp = Array.make (n + 1) 0 in
  for i = 1 to n do
    for j = 1 to i do
      if j <= Array.length prices then
        dp.(i) <- max dp.(i) (prices.(j - 1) + dp.(i - j))
    done
  done;
  dp.(n)

(* Approach 2: Top-down with memoization *)
let rod_cut_memo prices n =
  let cache = Hashtbl.create 32 in
  let rec solve len =
    if len = 0 then 0
    else
      match Hashtbl.find_opt cache len with
      | Some v -> v
      | None ->
        let best = ref 0 in
        for j = 1 to min len (Array.length prices) do
          best := max !best (prices.(j - 1) + solve (len - j))
        done;
        Hashtbl.add cache len !best;
        !best
  in
  solve n

(* Approach 3: With cut reconstruction *)
let rod_cut_with_cuts prices n =
  let dp = Array.make (n + 1) 0 in
  let cuts = Array.make (n + 1) 0 in
  for i = 1 to n do
    for j = 1 to min i (Array.length prices) do
      let val_ = prices.(j - 1) + dp.(i - j) in
      if val_ > dp.(i) then begin
        dp.(i) <- val_;
        cuts.(i) <- j
      end
    done
  done;
  (* Reconstruct cuts *)
  let result = ref [] in
  let remaining = ref n in
  while !remaining > 0 do
    result := cuts.(!remaining) :: !result;
    remaining := !remaining - cuts.(!remaining)
  done;
  (dp.(n), List.rev !result)

let () =
  let prices = [|1; 5; 8; 9; 10; 17; 17; 20|] in
  assert (rod_cut_dp prices 8 = 22);
  assert (rod_cut_dp prices 4 = 10);
  assert (rod_cut_memo prices 8 = 22);
  assert (rod_cut_memo prices 4 = 10);
  let (revenue, _cuts) = rod_cut_with_cuts prices 8 in
  assert (revenue = 22);

  let prices2 = [|3; 5; 8; 9; 10; 17; 17; 20|] in
  assert (rod_cut_dp prices2 4 = 12);

  Printf.printf "✓ All tests passed\n"

✓ Tests Rust test suite

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

    #[test]
    fn test_rod_cut_dp() {
        assert_eq!(rod_cut_dp(&[1, 5, 8, 9, 10, 17, 17, 20], 8), 22);
        assert_eq!(rod_cut_dp(&[1, 5, 8, 9, 10, 17, 17, 20], 4), 10);
        assert_eq!(rod_cut_dp(&[3, 5, 8, 9, 10, 17, 17, 20], 4), 12);
    }

    #[test]
    fn test_rod_cut_memo() {
        assert_eq!(rod_cut_memo(&[1, 5, 8, 9, 10, 17, 17, 20], 8), 22);
        assert_eq!(rod_cut_memo(&[1, 5, 8, 9, 10, 17, 17, 20], 4), 10);
    }

    #[test]
    fn test_rod_cut_with_cuts() {
        let (revenue, cuts) = rod_cut_with_cuts(&[1, 5, 8, 9, 10, 17, 17, 20], 8);
        assert_eq!(revenue, 22);
        assert_eq!(cuts.iter().sum::<usize>(), 8);
    }
}

Deep Comparison

Rod Cutting — Comparison

Core Insight

Rod cutting maximizes revenue by trying every possible first cut. It's equivalent to unbounded knapsack where items (cut lengths) can be reused. Cut reconstruction uses a parallel array tracking which cut was optimal at each length.

OCaml Approach

• Imperative loops with Array for DP table

• ref cells for tracking best and remaining in reconstruction

• List.rev to reverse the accumulated cuts list

• min for bounding loop range

Rust Approach

• vec! DP table with method-chained .max()

• HashMap for memoization

• Vec for cut reconstruction with push

• .min() method on usize for range bounding

Comparison Table

Aspect	OCaml	Rust
Range bound	`min i (Array.length prices)`	`i.min(prices.len())`
Cut tracking	Parallel `cuts` array + `ref` reconstruction	Parallel `cuts` vec + `while` loop
List building	Prepend `::` + `List.rev`	`Vec::push` (already in order)
Inner loop	`for j = 1 to min i len`	`for j in 1..=i.min(len)`

Exercises

Add a fixed_cost_per_cut: i64 parameter representing the cost of each cut operation. Modify the DP to subtract this cost each time a cut is made.

Implement rod_cut_bounded(prices: &[i64], max_pieces: usize) -> i64 where the rod can be cut into at most max_pieces pieces.

Write a test that verifies the rod cutting solution against the brute-force solution for all rods of length 1–10.

Open Source Repos

functional-rust

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

Rust