Dynamic Programming — Memoization

Introduction

Welcome to Phase 4: Advanced Techniques. So far, we have looked at specific data structures like Trees and Graphs. Now, we are looking at strategies for solving complex problems.

The crown jewel of algorithmic problem-solving is Dynamic Programming (DP).

DP is an intimidating name for a simple concept: breaking a large problem down into smaller sub-problems, solving those sub-problems, and storing the answers so you never have to solve them again.

There are two main ways to do DP:

1. Top-Down (Memoization): Covered in this post.
2. Bottom-Up (Tabulation): Covered in the next post.

The Problem: The Fibonacci Sequence

To understand DP, we must first look at a problem that desperately needs it.

The Fibonacci sequence is defined as $F(n) = F(n-1) + F(n-2)$, where $F(0) = 0$ and $F(1) = 1$. The sequence goes: 0, 1, 1, 2, 3, 5, 8, 13, 21...

Let’s write a standard recursive algorithm to find the $n^{th}$ Fibonacci number.

public int fib(int n) {
    if (n <= 1) return n; // base cases: fib(0)=0, fib(1)=1
    
    return fib(n - 1) + fib(n - 2);
}

The Disaster of Overlapping Sub-problems

The code above is beautiful, but if you run fib(50), your computer will freeze for minutes. Why? Let’s look at the recursion tree for fib(5).

Notice how f(3) (in red) is calculated twice. f(2) (in blue) is calculated three times.

For fib(5), we make 15 function calls to calculate just 6 unique numbers. For fib(50), we make over 20 billion function calls! This is $O(2^n)$ exponential time.

The Solution: Memoization

“Memoization” comes from the word “memorandum” (to remember).

Instead of blindly calculating fib(3) every time we see it, what if we stored the answer the very first time we calculated it? The next time we need fib(3), we just look up the answer in our “memo” pad.

We can use an Array or a Hash Map as our memo.

Step-by-Step Memoization

1. Create a memo (Array/HashMap) to store results.
2. Before doing any calculation in your recursive function, check the memo. If the answer is there, return it immediately!
3. If the answer is not there, do the calculation.
4. Before returning the result, save it in the memo.

Java Implementation

import java.util.HashMap;
import java.util.Map;

public class FibonacciMemo {

    // Our "memo" pad. Keys are 'n', Values are the Fibonacci result.
    private static Map<Integer, Long> memo = new HashMap<>();

    public static long fibMemo(int n) {
        // Base cases
        if (n <= 1) return n;

        // Step 1: Check the memo!
        if (memo.containsKey(n)) {
            return memo.get(n); // Instant O(1) return
        }

        // Step 2: Not in memo. We must calculate it.
        long result = fibMemo(n - 1) + fibMemo(n - 2);

        // Step 3: Save to memo BEFORE returning
        memo.put(n, result);

        return result;
    }

    public static void main(String[] args) {
        // This would take years without memoization.
        // With memoization, it runs in less than a millisecond.
        System.out.println(fibMemo(50)); // Output: 12586269025
    }
}

Complexity

The Two Requirements for DP

You cannot use DP on just any recursive problem. The problem MUST have two properties:

1. Optimal Substructure: The optimal solution to the big problem can be built from optimal solutions to its sub-problems. (e.g., The shortest path from A to C via B is made of the shortest path from A to B + the shortest path from B to C).
2. Overlapping Sub-problems: The problem breaks down into sub-problems that are reused multiple times (like fib(3) in our tree). If sub-problems do not overlap, you just have standard recursion/Divide and Conquer (like Merge Sort).

Taking it 2D: The 0/1 Knapsack Problem

Memoization works perfectly for multi-variable state too.

Imagine you are a thief with a backpack that can hold W kilograms. You have smaller items, each with a weight and a value. You want to maximise the total value without busting the weight limit.

Your recursive state needs two variables: (currentIndex, remainingWeight).

// A 2D Integer array acts as our Memo. null means uncalculated.
Integer[][] memo = new Integer[items.length][maxWeight + 1];

public int knapsack(int i, int w) {
    if (i >= items.length || w == 0) return 0; // Base cases
    
    // Check memo! (Notice we use 2D coordinates)
    if (memo[i][w] != null) return memo[i][w];
    
    // Choice 1: Skip the item
    int skip = knapsack(i + 1, w);
    
    // Choice 2: Take the item (if it fits)
    int take = 0;
    if (items[i].weight <= w) {
        take = items[i].value + knapsack(i + 1, w - items[i].weight);
    }
    
    // Save to memo and return the best choice
    memo[i][w] = Math.max(take, skip);
    return memo[i][w];
}

Practice Problems

1. Climbing Stairs – LeetCode #70 — The definitive beginner DP problem. (Spoiler: It’s just Fibonacci in disguise).
2. House Robber – LeetCode #198 — Learn how to make the “take it or skip it” decision.
3. Longest Increasing Subsequence – LeetCode #300 — A classic 2D DP problem that tests your ability to define the state.

What’s Next?

Memoization (Top-Down) is highly intuitive because you start at the end goal (fib(50)) and ask for what you need.

But it has a downside: deep recursion risks StackOverflowErrors. In the next post, we will flip the problem upside down and build our answers from the ground up using Bottom-Up Tabulation.