Lesson 1 · Dynamic programming

Memoization

Dynamic Programming solves complex problems by breaking them down into overlapping subproblems. Memoization does this top-down with recursion; Tabulation does it bottom-up with loops.

Overlapping Subproblems

Dynamic programming (DP) applies to problems that can be broken into smaller subproblems which are evaluated multiple times.

For example, in computing the 5th Fibonacci number, the 3rd Fibonacci number is evaluated twice. Without DP, this redundancy causes an exponential O(2^N) time explosion.

Subproblems are evaluated repeatedly
Causes exponential time growth
DP eliminates redundant work

Memoization (Top-Down)

Memoization starts with the main problem and recursively calls smaller subproblems. Before making a recursive call, it checks a cache (hash map or array).

If the subproblem was already solved, it returns the cached result immediately. If not, it calculates it, caches it, and returns it. This naturally only evaluates the necessary subproblems.

Recursive approach
Check cache before calculating
Only calculates what is strictly needed

Code example

Memoized Fibonacci cache hits and misses

cache = {0: 0, 1: 1}

def fib(n):
    if n in cache:
        return cache[n]
    cache[n] = fib(n - 1) + fib(n - 2)
    return cache[n]

print("fib(6) =", fib(6))

#include <iostream>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <algorithm>
#include <functional>
#include <tuple>
#include <array>
#include <numeric>
using namespace std;
map<int,int>c=
{
  {
    0,0
  }
  ,
  {
    1,1
  }
};
int fib(int n)
{
  if(c.count(n))return c[n];
  return c[n]=fib(n-1)+fib(n-2);
}
int main()
{
  cout<<"fib(6) = "<<fib(6);
}

import java.util.*;
class Main
{
  static Map<Integer,Integer>c=new HashMap<>();
  static int fib(int n)
  {
    if(c.containsKey(n))return c.get(n);
    int v=fib(n-1)+fib(n-2);
    c.put(n,v);
    return v;
  }
  public static void main(String[]z)
  {
    c.put(0,0);
    c.put(1,1);
    System.out.print("fib(6) = "+fib(6));
  }
}

Inputfib(6)

Outputfib(6) = 8

Example

Run the example step by step

Output

Tabulation (Bottom-Up)

Tabulation abandons recursion entirely. It starts with the absolute smallest base cases (e.g., Fib(0) and Fib(1)) and uses a loop to iteratively build up the solution in an array.

By the time the loop reaches the target N, all smaller dependencies have already been calculated and stored in the array.

Iterative approach (loops)
Starts from base cases
Fills an array sequentially

Trade-offs

Memoization is often easier to write because it closely follows the mathematical recurrence relation, and it skips evaluating unreachable subproblems.

However, Tabulation is generally faster in practice because it avoids the overhead of the recursive call stack and avoids stack-overflow errors on deep recursion. Tabulation also allows for memory optimization (state reduction).

Memoization: Intuitive, avoids unreachable states
Tabulation: No stack overhead, memory optimizable
Both have identical time complexity

The cache changes the computation graph

A recursive definition may call the same state through many paths. Memoization turns that recursion tree into a directed acyclic graph of distinct states: the first visit is a cache miss that computes dependencies, and every later visit is a cache hit that returns immediately.

Correct cache keys must contain every input that influences the result. Omitting a changing constraint merges different subproblems and returns plausible but incorrect values; including irrelevant mutable state destroys reuse.

Miss computes and stores
Hit returns without recursion
Keys encode the complete state

Costs, sentinels, and recursion limits

If there are S reachable states and each examines T transitions, memoized time is O(ST), not the size of the original recursion tree. Space includes S cached values plus recursion depth. Memoization may save work over tabulation when many theoretical states are unreachable.

Do not use a valid answer such as zero to mean 'not computed'. Check key membership or use a sentinel outside the answer domain. Cache immutable results, and consider iterative tabulation when dependency depth can overflow the call stack.

Count distinct states and transitions
Separate missing from cached zero
Recursion depth consumes space

Designing the state and cache lifetime

Start from a recurrence and name exactly the variables that determine a subproblem. Those variables form the cache key; local iteration counters and reconstructed paths usually do not. Store a result only after its dependencies are complete, unless the algorithm deliberately uses an in-progress marker to detect cycles. Decide whether the cache lives for one request or can safely be shared across requests with identical semantics.

Test a cached result equal to zero or false, repeated calls that should hit, unreachable theoretical states, and a dependency depth near the recursion limit. Instrumenting hits and misses reveals whether the intended overlap exists. Memoization does not automatically improve every recursion: when almost every state is unique it adds lookup overhead and memory without reducing calls, while bottom-up tabulation may improve locality when nearly all states are needed.

For concurrent callers, a shared mutable cache also needs synchronization or immutability guarantees. A race can compute a state twice or expose a partially constructed value even though the mathematical recurrence and single-threaded implementation are correct.

Derive keys from the recurrence
Separate in-progress from completed values
Measure whether repeated states actually occur