Recognising DP: Overlapping Sub-Problems
Identify when brute-force recursion re-solves the same sub-problem, draw the recursion tree for Fibonacci, and see the exponential blowup.
What is Dynamic Programming?
Dynamic programming (DP) solves complex problems by breaking them into simpler overlapping sub-problems, solving each sub-problem once, and storing the result to avoid redundant computation. DP applies when a problem has two ingredients: overlapping sub-problems (same sub-problem is solved multiple times in a naive recursion) and optimal substructure (the optimal solution can be built from optimal solutions to sub-problems). Without both ingredients, DP does not help.
# Two ingredients of DP:
# 1. Overlapping sub-problems:
# fib(5) -> fib(4) + fib(3)
# fib(4) -> fib(3) + fib(2) <- fib(3) computed twice!
# Without caching: O(2^n) calls for Fibonacci
# 2. Optimal substructure:
# Shortest path from A to C through B:
# shortest(A,C) = shortest(A,B) + shortest(B,C)
# The sub-path A->B must itself be the shortest
# Contrast with greedy: greedy makes one locally optimal
# choice; DP tries all choices and picks the best.
print('DP = overlapping sub-problems + optimal substructure')Fibonacci: The Classic DP Entry Point
The Fibonacci sequence (fib(n) = fib(n-1) + fib(n-2)) is the canonical example of overlapping sub-problems. The naive recursion has exponential time O(2^n) because it recomputes the same values repeatedly. The recursion tree for fib(6) shows fib(3) computed 3 times, fib(2) 5 times, and so on. This exponential blowup is exactly what DP eliminates by storing computed results.
import time
def fib_naive(n):
if n <= 1:
return n
return fib_naive(n-1) + fib_naive(n-2)
# Count the calls:
call_count = [0]
def fib_count(n):
call_count[0] += 1
if n <= 1: return n
return fib_count(n-1) + fib_count(n-2)
fib_count(10)
print(f'Calls for fib(10): {call_count[0]}') # 177 calls for n=10!
call_count[0] = 0
fib_count(20)
print(f'Calls for fib(20): {call_count[0]}') # 21891 calls
# n=30 -> ~2.7 million calls: exponential growthAll lessons in this course
- Recognising DP: Overlapping Sub-Problems
- Top-Down DP with Memoisation
- Bottom-Up DP with Tabulation
- Coin Change and Min-Cost Staircase