Dynamic Programming Basics

The Fibonacci sequence is the simplest example that demonstrates why dynamic programming is needed. A naive recursive solution recomputes the same values repeatedly, leading to exponential time complexity. Dynamic programming eliminates this redundancy.

Problem Definition

fib(0) = 0
fib(1) = 1
fib(n) = fib(n - 1) + fib(n - 2)

Naive Recursive Solution (Inefficient)

This is the version you already saw in recursion.

pub fn fib_recursive(n: u64) -> u64 {
    match n {
        0 => 0,
        1 => 1,
        _ => fib_recursive(n - 1) + fib_recursive(n - 2),
    }
}

Why This Is Slow

Calling fib(5) produces repeated calls:

fib(5)
├─ fib(4)
│  ├─ fib(3)
│  └─ fib(2)
└─ fib(3)
   ├─ fib(2)
   └─ fib(1)

Subproblems like fib(3) and fib(2) are recomputed many times.

Memoization (Top-Down DP)

Memoization stores the result of each subproblem so it is computed only once.

Rust Implementation (Memoization)

use std::collections::HashMap;

pub fn fib_memo(n: u64) -> u64 {
    let mut memo = HashMap::new();
    fib_helper(n, &mut memo)
}

fn fib_helper(n: u64, memo: &mut HashMap<u64, u64>) -> u64 {
    if let Some(&value) = memo.get(&n) {
        return value;
    }

    let result = match n {
        0 => 0,
        1 => 1,
        _ => fib_helper(n - 1, memo) + fib_helper(n - 2, memo),
    };

    memo.insert(n, result);
    result
}

Complexity (Memoization)

Tabulation (Bottom-Up DP)

Tabulation builds the solution iteratively from the base cases.

Rust Implementation (Tabulation)

pub fn fib_tab(n: usize) -> u64 {
    if n == 0 {
        return 0;
    }

    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]
}

Complexity (Tabulation)

Space Optimization

Since only the last two values are needed, space can be reduced to O(1).

Optimized Fibonacci

pub fn fib_optimized(n: u64) -> u64 {
    if n <= 1 {
        return n;
    }

    let mut prev2 = 0;
    let mut prev1 = 1;

    for _ in 2..=n {
        let current = prev1 + prev2;
        prev2 = prev1;
        prev1 = current;
    }

    prev1
}

Complexity (Optimized)

Comparing All Approaches

Key DP Takeaways

• DP avoids repeated work
• Memoization is recursion + cache
• Tabulation is iterative DP
• Space can often be optimized
• Fibonacci is the blueprint for many DP problems

Summary

• Fibonacci shows overlapping subproblems clearly
• Naive recursion is inefficient
• DP reduces exponential time to linear
• Memoization and tabulation are core DP techniques