Memoization and Dynamic Programming

The repeated-work problem

This recursion is correct and unusably slow:

static int fib(int n) {
    if (n <= 1) return n;
    return fib(n - 1) + fib(n - 2);
}

Trace fib(5) and the reason appears. fib(3) is computed twice, fib(2) three times, fib(1) five times. The tree of calls roughly doubles at each level, so fib(40) makes over a billion calls — nearly all of them recomputing values already known.

Nothing is wrong with the logic. The problem is that it has no memory.

Memoization

Store each result the first time you compute it, and return the stored value afterwards.

static long[] memo;

static long fib(int n) {
    if (n <= 1) return n;
    if (memo[n] != 0) return memo[n];      // already computed
    memo[n] = fib(n - 1) + fib(n - 2);     // compute once, remember
    return memo[n];
}

// caller:
memo = new long[50];
System.out.println(fib(45));

Each value is now computed exactly once, so fib(45) takes 45 steps instead of billions. The change is three lines.

long[] memo = new long[n + 1];
Arrays.fill(memo, -1);                  // -1 cannot be a valid count

if (memo[n] != -1) return memo[n];

Note the long. Fibonacci exceeds int around fib(47), and overflow gives a wrong answer with no error.

When memoization applies

Two conditions, both required:

Tabulation: the same thing bottom-up

Instead of recursing down and caching on the way back, fill a table from the smallest case upward.

static long fibTable(int n) {
    if (n <= 1) return n;

    long[] table = new long[n + 1];
    table[0] = 0;
    table[1] = 1;

    for (int i = 2; i <= n; i++) {
        table[i] = table[i - 1] + table[i - 2];
    }
    return table[n];
}

Same results, same amount of work, no recursion — so no stack-depth limit.

Memoization or tabulation

Write the recursion first, add memoisation to make it fast, and convert to a table only if you need the extra speed or hit a stack limit. Going straight to a table is harder because you must work out the correct fill order up front.

Reducing memory

Once tabulated, you often see that only the last few entries are ever used:

static long fibTwoVars(int n) {
    if (n <= 1) return n;

    long previous = 0, current = 1;
    for (int i = 2; i <= n; i++) {
        long next = previous + current;
        previous = current;
        current = next;
    }
    return current;
}

The table is gone entirely. This only works because each value depends on exactly the two before it — check that dependency before discarding rows.

A less artificial example

How many ways can you climb n stairs taking 1, 2, or 3 steps at a time?

The recurrence follows from the last step taken: it was 1, 2, or 3 steps, so the total is the sum of the ways to reach each of those positions.

static long countWays(int n) {
    long[] ways = new long[Math.max(n + 1, 4)];
    ways[0] = 1;                          // one way to stand still
    ways[1] = 1;
    ways[2] = 2;                          // 1+1, or 2

    for (int i = 3; i <= n; i++) {
        ways[i] = ways[i - 1] + ways[i - 2] + ways[i - 3];
    }
    return ways[n];
}

Setting ways[0] = 1 is the part that looks odd and matters most. There is exactly one way to be at the bottom — do nothing — and every later value depends on that being 1 rather than 0.

Grid paths

How many routes from the top-left to the bottom-right of a grid, moving only right or down, avoiding blocked cells?

static long countPaths(char[][] grid) {
    int rows = grid.length, cols = grid[0].length;
    long[][] paths = new long[rows][cols];

    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < cols; c++) {
            if (grid[r][c] == '#') {
                paths[r][c] = 0;                       // blocked
            } else if (r == 0 && c == 0) {
                paths[r][c] = 1;                       // start
            } else {
                long fromAbove = (r > 0) ? paths[r - 1][c] : 0;
                long fromLeft  = (c > 0) ? paths[r][c - 1] : 0;
                paths[r][c] = fromAbove + fromLeft;
            }
        }
    }
    return paths[rows - 1][cols - 1];
}

Row-by-row, left-to-right fill order works because every cell depends only on the one above and the one to its left — both already computed. Getting the fill order wrong reads uninitialised zeros and quietly gives wrong answers.

Finding the recurrence

The code is rarely the hard part. Working out the recurrence is.

Related

Going further