1059: Rod Cutting

Difficulty: Intermediate Category: Dynamic Programming Concept: Maximize revenue from cutting a rod into pieces with given prices per length Key Insight: Rod cutting is an unbounded knapsack variant — each length can be used multiple times. The recurrence `dp[i] = max(price[j] + dp[i-j])` for all valid j tries every first-cut position.

// 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)
}

fn main() {
    let prices = [1, 5, 8, 9, 10, 17, 17, 20];
    let (revenue, cuts) = rod_cut_with_cuts(&prices, 8);
    println!("Max revenue for rod of length 8: {} (cuts: {:?})", revenue, cuts);
}

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

📊 Detailed 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)`