Repeated Calls and the Memo Fix

Try plain fib(45) and it takes seconds. The reason: the same call is made again and again, and each time all its work is done from scratch.

See it

Press End to see the whole tree. Count how many times fib(3) and fib(2) appear.

fib(2) is solved three times. The tree grows about 1.6 times with each extra n:

But there are only n + 1 different calls. Billions of calls answer 46 questions.

Switch memo on

Memo = save the answer of each call, and never solve the same call twice. In the green nodes the answer comes from the table and the whole subtree is skipped.

When does memo help?

1. The answer depends only on the parameters (return style, no running total).
2. The same parameters repeat: the number of different calls is far smaller than the tree.

Quick test: multiply the ranges of the changing parameters. f(i, rem) with n = 100 and K = 1,000 has about 100,000 different calls, while the plain tree has 2¹⁰⁰. So memo helps a lot.

Add a memo in 4 steps

First write the plain recursion and test it. Then:

The logic in the middle does not change.

Example: climbing stairs (1 or 2 steps at a time; count the ways):

int[] memo;

int climbStairs(int n) {
    memo = new int[n + 1];
    Arrays.fill(memo, -1);                       // -1 = not solved yet
    return ways(n);
}

int ways(int n) {
    if (n == 0) return 1;                        // reached the top: one way
    if (n < 0) return 0;                         // overshot
    if (memo[n] != -1) return memo[n];           // solved before
    return memo[n] = ways(n - 1) + ways(n - 2);  // save, then return
}

From billions of calls down to O(n).

Java details that cause wrong answers

• “Not solved” value. Use -1 only if -1 can never be a real answer. Otherwise use Integer[] with null.
• Booleans. boolean[] has no “unknown”. Use Boolean[] (null = unknown).
• 2-D arrays. Fill row by row: for (int[] row : memo) Arrays.fill(row, -1);. Arrays.fill(memo, -1) compiles, but throws ArrayStoreException when it runs.
• Big answers. Use long, or apply % MOD on every addition if the question asks for it.
• Fresh memo. Create the memo inside the public method, so each test starts clean.
• Negative parameters. Shift them: memo[i][diff + OFFSET].

Time = number of different calls × work per call. For example, stairs is O(n) and f(i, rem) is O(n · K).

Your turn