Dynamic Programming

Phase 1f(x)

The Mathematics

Optimal substructure, overlapping subproblems, and the Fibonacci example

Two Key Properties

Dynamic Programming applies when a problem has:

1. Optimal Substructure: An optimal solution contains optimal solutions to subproblems.

2. Overlapping Subproblems: The same subproblems are solved repeatedly in a naive recursive approach.

Fibonacci: The Classic Example

The Fibonacci sequence is defined by the recurrence:

F(n) = F(n-1) + F(n-2), \quad F(0) = 0,\; F(1) = 1

This has both properties: $F(n)$ depends on smaller subproblems ( $F(n{-}1), F(n{-}2)$ ), and the same values are recomputed many times.

Naive Recursion: Exponential

A direct recursive implementation computes the same subproblems repeatedly. The call tree grows exponentially:

T(n) = T(n{-}1) + T(n{-}2) + O(1) = O(2^n)

For $F(7)$ , the naive approach makes 41 calls. $F(3)$ alone is computed 5 times!

Bottom-Up DP: Linear

Instead, fill a table from the base cases up. Each subproblem is computed exactly once:

\text{dp}[i] = \text{dp}[i{-}1] + \text{dp}[i{-}2] \quad \text{for } i = 2, \ldots, n

T(n) = O(n),\quad S(n) = O(n)

DP trades space for time: by storing $n+1$ values in a table, we eliminate all redundant computation. This is the essence of memoization (top-down) or tabulation (bottom-up).

Phase 2▶

See It Work

Computing Fibonacci(7) with bottom-up DP

Computing

Dependency

Computed

F(n) = F(n{-}1) + F(n{-}2),\; F(0) = 0,\; F(1) = 1

Step 1 of 8

Compute Fibonacci(7) using bottom-up DP. Allocate a table of size 8 to store subproblem results.

Phase 3</>

The Code

Mapping the Fibonacci recurrence to bottom-up Python

Mathematical Formulation

n \leq 1 \Rightarrow F(n) = n

Base case: F(0) = 0 and F(1) = 1

\text{dp}[0..n] \;\text{(table)}

Allocate array to store solutions to all subproblems

F(i) = F(i{-}1) + F(i{-}2)

Fill table bottom-up using the recurrence relation

O(n) \text{ time, } O(n) \text{ space}

Each subproblem computed once — linear time and space

T(n) = T(n{-}1) + T(n{-}2) = O(2^n)

Naive recursion: exponential due to overlapping subproblems

Python Implementation

def fib_dp(n):
    if n <= 1: return n
    dp = [0] * (n + 1)              # Allocate table
    dp[0], dp[1] = 0, 1             # Base cases
    for i in range(2, n + 1):
        dp[i] = dp[i-1] + dp[i-2]   # Recurrence
    return dp[n]                     # Answer

# Naive recursive (exponential!)
def fib_naive(n):
    if n <= 1: return n
    return fib_naive(n-1) + fib_naive(n-2)