1052 Intermediate

1052-fibonacci-dp — Fibonacci Bottom-Up DP

Functional Programming

Tutorial

The Problem

Bottom-up dynamic programming fills a table iteratively from the smallest sub-problems to the largest, avoiding recursion stack overhead and the overhead of hash map lookups in top-down memoization. For Fibonacci, this means filling an array from index 0 upward.

The classic space optimization reduces the O(n) array to O(1) space by observing that fib(n) depends only on the two previous values — keeping just two variables suffices.

🎯 Learning Outcomes

• Implement Fibonacci with a Vec-based DP table (O(n) space)

• Optimize to O(1) space using two rolling variables

• Express the same computation as an iterator/fold

• Understand when O(n) table is needed (path reconstruction) vs O(1) is sufficient

• Connect to the general DP pattern: define sub-problems, fill bottom-up

Code Example

#![allow(clippy::all)]
// 1052: Fibonacci Bottom-Up DP with O(1) Space

// Approach 1: Vec-based bottom-up DP
fn fib_vec(n: usize) -> u64 {
    if n <= 1 {
        return n as u64;
    }
    let mut dp = vec![0u64; n + 1];
    dp[1] = 1;
    for i in 2..=n {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    dp[n]
}

// Approach 2: O(1) space — two variables
fn fib_const(n: usize) -> u64 {
    if n <= 1 {
        return n as u64;
    }
    let (mut a, mut b) = (0u64, 1u64);
    for _ in 2..=n {
        let t = a + b;
        a = b;
        b = t;
    }
    b
}

// Approach 3: Iterator/fold approach
fn fib_fold(n: usize) -> u64 {
    if n <= 1 {
        return n as u64;
    }
    let (_, b) = (2..=n).fold((0u64, 1u64), |(a, b), _| (b, a + b));
    b
}

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

    const CASES: &[(usize, u64)] = &[
        (0, 0),
        (1, 1),
        (2, 1),
        (5, 5),
        (10, 55),
        (20, 6765),
        (30, 832040),
    ];

    #[test]
    fn test_fib_vec() {
        for &(n, expected) in CASES {
            assert_eq!(fib_vec(n), expected, "fib_vec({n})");
        }
    }

    #[test]
    fn test_fib_const() {
        for &(n, expected) in CASES {
            assert_eq!(fib_const(n), expected, "fib_const({n})");
        }
    }

    #[test]
    fn test_fib_fold() {
        for &(n, expected) in CASES {
            assert_eq!(fib_fold(n), expected, "fib_fold({n})");
        }
    }
}

(* 1052: Fibonacci Bottom-Up DP with O(1) Space *)

(* Approach 1: Array-based bottom-up DP *)
let fib_array n =
  if n <= 1 then n
  else begin
    let dp = Array.make (n + 1) 0 in
    dp.(1) <- 1;
    for i = 2 to n do
      dp.(i) <- dp.(i - 1) + dp.(i - 2)
    done;
    dp.(n)
  end

(* Approach 2: O(1) space — two variables *)
let fib_const n =
  if n <= 1 then n
  else begin
    let a = ref 0 in
    let b = ref 1 in
    for _ = 2 to n do
      let t = !a + !b in
      a := !b;
      b := t
    done;
    !b
  end

(* Approach 3: Functional fold with tuple *)
let fib_fold n =
  if n <= 1 then n
  else
    let (_, b) =
      List.init (n - 1) Fun.id
      |> List.fold_left (fun (a, b) _ -> (b, a + b)) (0, 1)
    in
    b

let () =
  List.iter (fun (n, expected) ->
    assert (fib_array n = expected);
    assert (fib_const n = expected);
    assert (fib_fold n = expected)
  ) [(0, 0); (1, 1); (2, 1); (5, 5); (10, 55); (20, 6765); (30, 832040)];
  Printf.printf "✓ All tests passed\n"

Key Differences

Tail recursion: OCaml's tail-recursive fib is idiomatic and stack-safe; Rust's iterative version achieves the same without tail-call optimization (which Rust does not guarantee).

Fold idiom: Rust's fold((0, 1), |(a, b), _| (b, a+b)) is a compact functional expression; OCaml's equivalent is a tail-recursive fold.

Overflow behavior: Rust's u64 panics on overflow in debug mode; OCaml's int wraps silently. Use u64::checked_add for safe overflow detection in Rust.

Table vs rolling: Both languages can use either the table or the rolling variable approach — the choice depends on whether intermediate values are needed.

OCaml Approach

OCaml's bottom-up Fibonacci:

let fib_dp n =
  if n <= 1 then n
  else
    let arr = Array.make (n + 1) 0 in
    arr.(1) <- 1;
    for i = 2 to n do
      arr.(i) <- arr.(i-1) + arr.(i-2)
    done;
    arr.(n)

(* O(1) space version *)
let fib n =
  let rec go a b = function
    | 0 -> a
    | n -> go b (a + b) (n - 1)
  in
  go 0 1 n

OCaml's tail-recursive version is naturally O(1) space and stack-safe. Rust's iterative version avoids stack overflow for the same reason.

Full Source

#![allow(clippy::all)]
// 1052: Fibonacci Bottom-Up DP with O(1) Space

// Approach 1: Vec-based bottom-up DP
fn fib_vec(n: usize) -> u64 {
    if n <= 1 {
        return n as u64;
    }
    let mut dp = vec![0u64; n + 1];
    dp[1] = 1;
    for i in 2..=n {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    dp[n]
}

// Approach 2: O(1) space — two variables
fn fib_const(n: usize) -> u64 {
    if n <= 1 {
        return n as u64;
    }
    let (mut a, mut b) = (0u64, 1u64);
    for _ in 2..=n {
        let t = a + b;
        a = b;
        b = t;
    }
    b
}

// Approach 3: Iterator/fold approach
fn fib_fold(n: usize) -> u64 {
    if n <= 1 {
        return n as u64;
    }
    let (_, b) = (2..=n).fold((0u64, 1u64), |(a, b), _| (b, a + b));
    b
}

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

    const CASES: &[(usize, u64)] = &[
        (0, 0),
        (1, 1),
        (2, 1),
        (5, 5),
        (10, 55),
        (20, 6765),
        (30, 832040),
    ];

    #[test]
    fn test_fib_vec() {
        for &(n, expected) in CASES {
            assert_eq!(fib_vec(n), expected, "fib_vec({n})");
        }
    }

    #[test]
    fn test_fib_const() {
        for &(n, expected) in CASES {
            assert_eq!(fib_const(n), expected, "fib_const({n})");
        }
    }

    #[test]
    fn test_fib_fold() {
        for &(n, expected) in CASES {
            assert_eq!(fib_fold(n), expected, "fib_fold({n})");
        }
    }
}

(* 1052: Fibonacci Bottom-Up DP with O(1) Space *)

(* Approach 1: Array-based bottom-up DP *)
let fib_array n =
  if n <= 1 then n
  else begin
    let dp = Array.make (n + 1) 0 in
    dp.(1) <- 1;
    for i = 2 to n do
      dp.(i) <- dp.(i - 1) + dp.(i - 2)
    done;
    dp.(n)
  end

(* Approach 2: O(1) space — two variables *)
let fib_const n =
  if n <= 1 then n
  else begin
    let a = ref 0 in
    let b = ref 1 in
    for _ = 2 to n do
      let t = !a + !b in
      a := !b;
      b := t
    done;
    !b
  end

(* Approach 3: Functional fold with tuple *)
let fib_fold n =
  if n <= 1 then n
  else
    let (_, b) =
      List.init (n - 1) Fun.id
      |> List.fold_left (fun (a, b) _ -> (b, a + b)) (0, 1)
    in
    b

let () =
  List.iter (fun (n, expected) ->
    assert (fib_array n = expected);
    assert (fib_const n = expected);
    assert (fib_fold n = expected)
  ) [(0, 0); (1, 1); (2, 1); (5, 5); (10, 55); (20, 6765); (30, 832040)];
  Printf.printf "✓ All tests passed\n"

✓ Tests Rust test suite

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

    const CASES: &[(usize, u64)] = &[
        (0, 0),
        (1, 1),
        (2, 1),
        (5, 5),
        (10, 55),
        (20, 6765),
        (30, 832040),
    ];

    #[test]
    fn test_fib_vec() {
        for &(n, expected) in CASES {
            assert_eq!(fib_vec(n), expected, "fib_vec({n})");
        }
    }

    #[test]
    fn test_fib_const() {
        for &(n, expected) in CASES {
            assert_eq!(fib_const(n), expected, "fib_const({n})");
        }
    }

    #[test]
    fn test_fib_fold() {
        for &(n, expected) in CASES {
            assert_eq!(fib_fold(n), expected, "fib_fold({n})");
        }
    }
}

Deep Comparison

Fibonacci Bottom-Up DP — Comparison

Core Insight

Bottom-up DP eliminates recursion overhead. The O(1) space variant using tuple state (a, b) → (b, a+b) is naturally expressed as a fold in both languages, showing how functional patterns align with space-optimal DP.

OCaml Approach

• Array-based DP with imperative for loop and mutable array

• ref cells for the two-variable version (imperative in functional clothing)

• List.fold_left with tuple destructuring for the pure functional version

• List.init creates the iteration range

Rust Approach

• Vec-based DP table — explicit allocation, indexed access

• Tuple destructuring let (mut a, mut b) for O(1) space

• (2..=n).fold((0, 1), |(a, b), _| (b, a+b)) — idiomatic iterator chain

• Range iterators are zero-cost abstractions

Comparison Table

Aspect	OCaml	Rust
Array DP	`Array.make n 0`	`vec![0u64; n + 1]`
Mutable vars	`ref` cells + `:=`	`let mut` + `=`
Fold syntax	`List.fold_left (fun (a,b) _ -> ...)`	`(2..=n).fold((0,1), \\|(a,b), _\\| ...)`
Range creation	`List.init (n-1) Fun.id` (allocates list)	`2..=n` (zero-cost iterator)
Space complexity	Same O(1) for both	Same O(1) for both
Overflow handling	Silent overflow (OCaml ints)	Panic on debug, wrap on release

Exercises

Implement fib_matrix(n: u64) -> u64 using matrix exponentiation for O(log n) time complexity.

Generalize fib_fold into a linear_recurrence(coeffs: &[i64], init: &[i64], n: usize) -> i64 for any linear recurrence.

Write fib_pairs(n: usize) -> Vec<(u64, u64)> that returns all (fib(i), fib(i+1)) pairs up to n using the rolling-variable approach.

Open Source Repos

functional-rust

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

Rust