Dynamic Programming

First PublishedFeb 11, 2026ByAtif Alam

Difficulty: High. ROI: Medium.

Other common names: DP, memoization (top-down + cache).

When to use: Use when the problem has overlapping subproblems and optimal substructure (e.g. Fibonacci, shortest path, knapsack, longest common subsequence). You store results of subproblems so you don’t recompute them.

Idea: Either top-down (recurse and cache results) or bottom-up (fill a table in order so that when you compute a cell, the subproblems it needs are already computed).

Time / space: Often reduces exponential brute-force to polynomial (e.g. O(n^2) or O(n * W)). Space proportional to state size.

Example #1 — Fibonacci with Memoization

Compute the nth Fibonacci number by recursing with a shared cache: when we’ve already computed fib(k), return the stored value instead of recursing again.

Sample input and output

print(fib(5))   # 5
print(fib(10))  # 55

• Sample input: n = 5.
• Sample output: 5 — the 5th Fibonacci number (0, 1, 1, 2, 3, 5).

Code (with inline comments)

# Fibonacci with memoization (top-down DP)
def fib(n, memo=None):
    if memo is None:
        memo = {}   # shared cache so we reuse results across recursive calls
    if n in memo:
        return memo[n]   # already computed — avoid redundant work
    if n <= 1:
        return n
    memo[n] = fib(n - 1, memo) + fib(n - 2, memo)
    return memo[n]

Line-by-line:

• memo = {} — A dict (dictionary) maps keys to values. We use it as a cache: memo[n] will store the result of fib(n) so we don’t recompute it. We only create it on the first call (memo is None); recursive calls share the same dict.
• if n in memo: return memo[n] — This is the memoization step: if we’ve already computed fib(n), return the stored value instead of recursing again. That turns exponential recursion into O(n) time.
• if n <= 1: return n — Base case: fib(0)=0, fib(1)=1.
• memo[n] = fib(n - 1, memo) + fib(n - 2, memo) — Compute fib(n) by the recurrence, store it in the cache, then return it. Both recursive calls use the same memo, so their results are reused.

Execution trace (numbered list)

For fib(5), we compute each n at most once and fill memo in dependency order:

1. Step 1: fib(0)=0, fib(1)=1 (base cases).
2. Step 2: fib(2)=fib(1)+fib(0)=1+0=1, memo[2]=1.
3. Step 3: fib(3)=fib(2)+fib(1)=1+1=2, memo[3]=2.
4. Step 4: fib(4)=fib(3)+fib(2)=2+1=3, memo[4]=3.
5. Step 5: fib(5)=fib(4)+fib(3)=3+2=5, return 5.

Execution trace (code with step comments)

# fib(5) → need fib(4), fib(3)
#   fib(4) → need fib(3), fib(2)
#     fib(3) → need fib(2), fib(1) → memo[2]=1, memo[3]=2
#     fib(2) → in memo → 1
#   memo[4]=3
#   fib(3) → in memo → 2
# memo[5]=5, return 5

Execution trace (ASCII diagram)

Dependency order: each fib(n) depends on fib(n-1) and fib(n-2); memo avoids recomputation.

fib(5)
  ├── fib(4) → 3
  │     ├── fib(3) → 2
  │     │     ├── fib(2) → 1
  │     │     └── fib(1) → 1
  │     └── fib(2) → 1 (cached)
  └── fib(3) → 2 (cached)
memo: {0:0, 1:1, 2:1, 3:2, 4:3, 5:5}