Lesson 28.1 · DP Foundations: 1D

From Recursion to Memoisation

If a recursive function is called with the same arguments many times, cache each result the first time it's computed. The work drops to (number of distinct states) × (work per state).

14 min

Think of it like this

A student who writes every answered homework question in a notebook. When the same question comes up again, they copy the answer instead of solving it from scratch.

1.The waste in plain recursion

fib(n) = fib(n − 1) + fib(n − 2) calls fib(n − 2) twice, fib(n − 3) three times, fib(n − 4) five times… The call count itself grows like the Fibonacci numbers: about 1.6ⁿ. Yet there are only n + 1 different questions (fib(0) to fib(n)).

Memoisation (top-down DP): before computing, check a cache; after computing, store the result. Each distinct state is solved once, so fib(n) needs O(n) time and O(n) memory.

Two conditions make DP work: overlapping subproblems (the same smaller questions repeat) and optimal substructure (the best answer is built from best answers to smaller questions).

Main.java

public class Main {
    static long naiveCalls = 0, memoCalls = 0;
    static long[] memo = new long[31];

    static long naive(int n) {
        naiveCalls++;
        if (n < 2) return n;
        return naive(n - 1) + naive(n - 2);
    }

    static long fast(int n) {
        memoCalls++;
        if (n < 2) return n;
        if (memo[n] != 0) return memo[n];          // already solved
        return memo[n] = fast(n - 1) + fast(n - 2);
    }

    public static void main(String[] args) {
        System.out.println("naive: " + naive(30) + " in " + naiveCalls + " calls");
        System.out.println("memo:  " + fast(30) + " in " + memoCalls + " calls");
    }
}

Output

naive: 832040 in 2692537 calls
memo:  832040 in 59 calls

Remember

Cache by the function's arguments (the state).
Time = states × work per state.
Needs overlapping subproblems and optimal substructure.

Common mistakes

Caching with a sentinel value that can be a real answer (use a separate boolean[] or Integer null).
Including unchanging parameters in the state.

Words used in this lesson

Dynamic programming: Solving a problem by combining stored answers to smaller versions of it.
Memoisation: Top-down DP: recursion plus a cache of results.
State: The minimum information that identifies a subproblem, e.g. the index i.

Command Palette

From Recursion to Memoisation

1.The waste in plain recursion