Dynamic programming: overlapping subproblems, memoisation and tables

← Back to the section

Recursion reduces a task to a simpler version of itself. Sometimes that works beautifully, and sometimes the program hangs solid on an input of forty elements. Why it happens and how it is fixed — the technique is called dynamic programming.

The problem: the same value is computed again and again

The classic example is the Fibonacci numbers: each one is the sum of the two before it.

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

The code repeats the definition and is completely unusable: fib(50) runs for minutes. The reason shows up in the call tree: computing fib(5) needs fib(4) and fib(3), but fib(4) computes fib(3) again on its own, and that one computes fib(2) again. The number of calls grows by roughly a factor of 1.6 per step. That sounds small, but the growth is exponential: fib(50) piles up about forty billion calls.

The key observation: the subproblems overlap. There are few of them — only n — but naive recursion does not remember what it has already computed.

Memoisation: just remember

The most direct cure is to keep a notebook and write down what has been computed. The program runs fib both ways and prints how many calls each one took:

live example

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

public class FibCalls {
    static long naiveCalls, memoCalls;

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

    static long memo(int n, Map<Integer, Long> known) {
        memoCalls++;
        if (n <= 1) return n;
        Long ready = known.get(n);
        if (ready != null) return ready;
        long value = memo(n - 1, known) + memo(n - 2, known);
        known.put(n, value);
        return value;
    }

    public static void main(String[] args) {
        for (int n : new int[]{10, 20, 30}) {
            naiveCalls = memoCalls = 0;
            naive(n);
            memo(n, new HashMap<>());
            System.out.println("fib(" + n + "): naive " + naiveCalls
                    + ", with a notebook " + memoCalls);
        }
    }
}

Three lines changed, and the cost dropped from exponential to O(n): every value is computed exactly once and then read from the notebook. On fib(30) that is 59 calls instead of almost three million. This approach is called "top-down": we still go from the big task to the small ones, we just stop repeating ourselves.

A table: bottom-up

If the subproblems can be ordered so that each one relies only on already computed ones, recursion is not needed at all — it is enough to fill a table in order:

static long fib(int n) {
    if (n <= 1) return n;
    long[] dp = new long[n + 1];
    dp[1] = 1;
    for (int i = 2; i <= n; i++) dp[i] = dp[i - 1] + dp[i - 2];
    return dp[n];
}

That is "bottom-up". It runs faster (no call overhead) and never risks overflowing the stack. The price is that the right filling order is now yours to find.

State and transition

An unfamiliar task is attacked by answering two questions.

What is the state? It is the set of parameters that fully describes a subproblem. For Fibonacci the state is a single number i. For the knapsack it is the pair "how many items have been considered" and "how much room is left".

What is the transition? It is the formula expressing the answer for a state through the answers for smaller ones. Plus the base cases — states whose answer is already known.

Take this task: warehouses stand along a road, each with its revenue, two neighbours in a row may not be collected from, and the largest total is wanted. The state is the warehouse number. The transition: a warehouse is either skipped (the answer stays the same as for the previous one) or taken — and then it adds to the answer from two steps back, because the neighbour could not be taken.

live example

public class Pickup {
    public static void main(String[] args) {
        int[] revenue = {2, 7, 9, 3, 1, 8, 4};
        int skip = 0;
        int take = 0;
        for (int money : revenue) {
            int next = Math.max(skip, take);
            take = skip + money;
            skip = next;
        }
        System.out.println("largest revenue: " + Math.max(skip, take));
    }
}

Here a common optimisation shows up: since a state depends only on the two states before it, the whole table collapses into two variables — O(1) memory instead of O(N).

Two dimensions: the knapsack

When the state is described by a pair of parameters, the table becomes two-dimensional. The classic case is the knapsack: the bag holds capacity kilograms, an item has a weight and a price, and it goes in whole or not at all.

The state is "the first i items have been considered, left room remains", and the answer is the largest price. The transition: either the item is not taken (the answer as for i-1), or it is taken — the item's price plus the answer for i-1 with reduced room.

This table can be collapsed too — down to a single row, but the inner loop must run right to left. Here are both versions side by side:

live example

public class Knapsack {
    public static void main(String[] args) {
        int[] weights = {3, 4, 5};
        int[] prices = {40, 50, 60};
        int capacity = 10;
        int[] once = new int[capacity + 1];
        int[] many = new int[capacity + 1];
        for (int i = 0; i < weights.length; i++) {
            for (int left = capacity; left >= weights[i]; left--) {
                once[left] = Math.max(once[left], once[left - weights[i]] + prices[i]);
            }
            for (int left = weights[i]; left <= capacity; left++) {
                many[left] = Math.max(many[left], many[left - weights[i]] + prices[i]);
            }
        }
        System.out.println("right to left: " + once[capacity]);
        System.out.println("left to right: " + many[capacity]);
    }
}

The answers differ: going left to right, the cell left - weights[i] already holds a result that includes the current item, so the item lands in the bag several times. That is a different task — the one where items may be taken repeatedly.

The cost is O(N · capacity). It looks polynomial, but that is deceptive: the size of the input is not the capacity itself but the length of its notation. A billion is ten digits, and every extra digit multiplies the work by ten. On very large capacities the technique stops saving you.

When the technique applies

Two properties are needed at once:

• overlapping subproblems — naive recursion solves the same thing many times over; if all subproblems are different, there is nothing to remember;
• optimal substructure — the answer is assembled from the answers for smaller subproblems; if an optimal answer requires a non-optimal solution of a subproblem, the transition formula is wrong.

Signs in the wording: the question asks for the number of ways or for a minimum and maximum over all variants, while the naive solution is a full search of "take it or leave it".

If at each step it is obvious what to take, and that never has to be reconsidered, a greedy pass without any table is enough.

In short

• Dynamic programming is a search that never repeats work it has already done.
• The condition for applying it: the subproblems overlap, and the answer is assembled from the answers to smaller subproblems.
• Memoisation ("top-down") is recursion plus a notebook: three new lines, and instead of millions of calls there are 2n-1.
• A table ("bottom-up") is filling in order without recursion: faster and with no risk of overflowing the stack.
• The design work boils down to two questions: what is the state, and what is the transition between states.
• In a collapsed table the direction of the inner loop decides whether an item can be taken repeatedly, and memory drops to O(1).

What to read next

• Recursion — where the call tree comes from.
• Maths for big-O — why growth of 1.6 per step kills a program while O(n) does not.
• Prefix sums — the same "compute once and remember" idea in its simplest form.
• Backtracking — what to do when the variants themselves are wanted, not their count or maximum.