Dynamic programming trades space for time. When a problem has optimal substructure (the best solution contains best sub-solutions) and overlapping subproblems (the same sub-solutions recur), store them in a table instead of recomputing.
Fibonacci: recursion vs DP
Naive recursion computes fib(n) in O(2^n). Memoization stores each value once: O(n) time, O(n) space. Bottom-up iteration: O(n) time, O(1) space.
Scheme
; Fibonacci: naive vs memoized; Naive recursion: exponential
(define (fib-naive n)
(if (<= n 1) n
(+ (fib-naive (- n 1)) (fib-naive (- n 2)))))
; Bottom-up DP: linear
(define (fib-dp n)
(if (<= n 1) n
(let loop ((i 2) (a 0) (b 1))
(if (= i n) (+ a b)
(loop (+ i 1) b (+ a b))))))
(display "fib(10) naive: ") (display (fib-naive 10)) (newline)
(display "fib(10) dp: ") (display (fib-dp 10)) (newline)
(display "fib(30) dp: ") (display (fib-dp 30)) (newline)
; fib(30) naive would take billions of calls
Python
# Fibonacci: three approachesfromfunctoolsimport lru_cache
# Memoized recursion@lru_cache(maxsize=None)def fib_memo(n):
if n <= 1: return n
return fib_memo(n-1) + fib_memo(n-2)
# Bottom-updef fib_dp(n):
if n <= 1: return n
a, b = 0, 1for _ inrange(2, n+1):
a, b = b, a+b
return b
print(f"fib(10) = {fib_dp(10)}")
print(f"fib(30) = {fib_dp(30)}")
print(f"fib(50) = {fib_dp(50)}")
Edit distance
Given two strings, find the minimum number of insertions, deletions, and replacements to transform one into the other. The DP table has size m x n. Each cell depends on three neighbors.
Scheme
; Edit distance (Levenshtein); dp[i][j] = edit distance of first i chars of s and first j chars of t
(define (edit-distance s t)
(let* ((m (string-length s))
(n (string-length t))
(dp (make-vector (* (+ m 1) (+ n 1)) 0)))
; Helper to index into flat vector
(define (idx i j) (+ (* i (+ n 1)) j))
; Base cases
(let iloop ((i 0))
(when (<= i m)
(vector-set! dp (idx i 0) i)
(iloop (+ i 1))))
(let jloop ((j 0))
(when (<= j n)
(vector-set! dp (idx 0 j) j)
(jloop (+ j 1))))
; Fill table
(let iloop ((i 1))
(when (<= i m)
(let jloop ((j 1))
(when (<= j n)
(let ((cost (if (char=? (string-ref s (- i 1))
(string-ref t (- j 1))) 01)))
(vector-set! dp (idx i j)
(min (+ (vector-ref dp (idx (- i 1) j)) 1)
(+ (vector-ref dp (idx i (- j 1))) 1)
(+ (vector-ref dp (idx (- i 1) (- j 1))) cost))))
(jloop (+ j 1))))
(iloop (+ i 1))))
(vector-ref dp (idx m n))))
(display "CAR -> CAT: ") (display (edit-distance "CAR""CAT")) (newline)
(display "kitten -> sitting: ") (display (edit-distance "kitten""sitting"))