Introduction
Dynamic programming (DP) is an optimization technique for solving problems by breaking them into smaller subproblems, solving each subproblem once, and reusing those results instead of recomputing them. A problem is a good candidate for DP only when it exhibits two properties: overlapping subproblems (the same smaller subproblem is solved repeatedly by naive recursion) and optimal substructure (an optimal solution to the problem can be constructed from optimal solutions to its subproblems). If either property is missing, plain recursion or a greedy/divide-and-conquer approach is usually more appropriate.
Cricket analogy: Instead of re-simulating a batter's full net session from scratch for every scenario, DP caches each partial-innings outcome once and reuses it, valid only when the same net-session subproblem recurs and an optimal full innings can be built from optimal partial innings.
Approach/Syntax
# Naive recursive Fibonacci: exponential time, recomputes the same values
def fib_naive(n):
if n <= 1:
return n
return fib_naive(n - 1) + fib_naive(n - 2)
# DP version using memoization: each subproblem solved exactly once
def fib_memo(n, cache=None):
if cache is None:
cache = {}
if n <= 1:
return n
if n in cache:
return cache[n]
cache[n] = fib_memo(n - 1, cache) + fib_memo(n - 2, cache)
return cache[n]Explanation
In fib_naive, computing fib(5) calls fib(4) and fib(3); fib(4) itself calls fib(3) and fib(2) — so fib(3) is computed twice, and this duplication grows exponentially with n. That duplication is the signature of overlapping subproblems. Optimal substructure holds here too: fib(n) is defined purely in terms of the optimal (in this case, the only) answers to fib(n-1) and fib(n-2). fib_memo exploits both properties by caching each result the first time it is computed and returning the cached value on every subsequent call, collapsing the exponential tree into linear work.
Cricket analogy: Simulating a batting-order projection naively recomputes the same partial-lineup outcome (like the 3rd-wicket scenario) multiple times as duplication grows exponentially, but caching each lineup outcome the first time collapses that repeated tree into linear work.
Example
call_count = 0
def fib_traced(n, cache=None):
global call_count
if cache is None:
cache = {}
call_count += 1
if n <= 1:
return n
if n in cache:
return cache[n]
cache[n] = fib_traced(n - 1, cache) + fib_traced(n - 2, cache)
return cache[n]
result = fib_traced(10)
print(f"fib(10) = {result}") # fib(10) = 55
print(f"function calls = {call_count}") # only 19 calls, vs 177 for fib_naive(10)Output/Complexity
Running the traced example prints 'fib(10) = 55' and 'function calls = 19'. The naive recursive version makes 177 calls for the same input because it recomputes overlapping subproblems repeatedly, giving it O(2^n) time complexity. The memoized version computes each of the n distinct subproblems exactly once, giving O(n) time and O(n) space for the cache plus recursion stack. This same n-fold speedup pattern — from exponential to polynomial — is what makes DP valuable for knapsack, LCS, coin change, and every other classic DP problem covered in this module.
Cricket analogy: A naive net-run-rate recalculation across 10 overs makes exponentially many repeated calls, like 177 redundant re-simulations, while a cached version computes each of the 10 distinct over-states exactly once, an exponential-to-linear speedup applicable to squad-selection and chase-planning DP problems.
Key Takeaways
- DP applies only when a problem has both overlapping subproblems and optimal substructure.
- Overlapping subproblems means naive recursion recomputes the same inputs many times.
- Optimal substructure means an optimal answer can be built from optimal answers to smaller instances.
- Caching (memoization) turns exponential-time recursive solutions into polynomial-time solutions.
- Always identify the recurrence relation first — the code follows naturally once the recurrence is correct.
Practice what you learned
1. Which two properties must a problem have for dynamic programming to be applicable?
2. Why is naive recursive Fibonacci inefficient?
3. What does 'optimal substructure' mean?
4. In fib_memo, what is the time complexity after caching, versus the naive version?
Was this page helpful?
You May Also Like
Memoization vs Tabulation
Compare the top-down (memoization) and bottom-up (tabulation) strategies for implementing dynamic programming solutions.
Recursion Basics
Learn how functions that call themselves can solve problems by breaking them into smaller subproblems.
0/1 Knapsack Problem
Learn the classic 0/1 knapsack DP formulation, its O(nW) recurrence, and how to reconstruct the chosen items.