Dynamic Programming: Introduction

Motivation

Consider the Fibonacci numbers: $F_0 = F_1 = 1$, $F_n = F_{n-1} + F_{n-2}$ for $n \ge 2$. A naive recursive implementation:

def f(n):
    if n < 2: return 1
    return f(n-2) + f(n-1)

The call tree is exponential: computing $F_5$ calls $F_4$ and $F_3$; computing $F_4$ also calls $F_3$, etc. The same subproblems are recomputed many times. The running time is $\Theta(2^n)$ — utterly impractical for $n > 50$.

Dynamic programming (DP) solves this by storing computed results and reusing them. The same Fibonacci computation drops to $\Theta(n)$.

When to Use DP

Two properties must hold:

1. Optimal substructure: An optimal solution to the problem contains within it optimal solutions to subproblems. Given a choice at each step, the best overall choice is composed of locally best choices.

2. Overlapping subproblems: The recursive solution revisits the same subproblems repeatedly. DP stores their solutions so each is solved only once.

Divide and conquer also exploits optimal substructure but assumes subproblems are disjoint (no overlap). DP handles the overlapping case.

Two Approaches

Top-Down (Memoisation)

Write the recursive solution. Before computing any subproblem, check a cache (memo table). If the result exists, return it; otherwise compute, cache, and return.

cache = {}
def f(n):
    if n in cache: return cache[n]
    if n < 2: res = 1
    else: res = f(n-2) + f(n-1)
    cache[n] = res
    return res

• Solves only subproblems actually needed.
• Requires stack space for recursion (depth proportional to $n$ for Fibonacci).

Bottom-Up (Tabulation)

Identify the dependency order of subproblems and fill the table iteratively from base cases upward.

def f(n):
    x = [1] * (n+1)
    for i in range(2, n+1):
        x[i] = x[i-2] + x[i-1]
    return x[n]

• Solves all subproblems up to $n$, even ones not strictly needed.
• No recursive stack overhead.
• Easier to analyse space and time.

Space can often be optimised. For Fibonacci, only the last two values are needed:

def f(n):
    x, y = 1, 1
    for _ in range(2, n+1):
        x, y = y, x + y
    return y

This reduces space from $\Theta(n)$ to $\Theta(1)$.

DP vs. Divide and Conquer

Aspect	Divide & Conquer	Dynamic Programming
Subproblem overlap	Disjoint (no overlap)	Significant overlap
Approach	Recursive, no cache	Recursive with cache (memoisation) or iterative (bottom-up)
Examples	Mergesort, quicksort, binary search	Fibonacci, LCS, matrix chain, rod cutting
Time saved by DP	None (no overlap to exploit)	Exponential → polynomial

The Naive Bellman Recursion Problem

General optimisation problems framed via the Bellman equation (choose optimal sequence of actions) suffer from the same exponential blow-up as Fibonacci when implemented naively. The computation tree grows exponentially with problem size, because the same states are reached through many different action sequences. DP is precisely the remedy.

Summary

Property	Value
Requirements	Optimal substructure + overlapping subproblems
Top-down	Recursion + memoisation cache
Bottom-up	Iterative table filling from base cases
Typical speed-up	Exponential → polynomial
Space vs. time	Often can reduce space by discarding unneeded table entries