Overlapping subproblems

Code in:JavaC#PythonJavaScript

In short: Dynamic programming solves each subproblem once and keeps the answer: with memoization top-down or a table bottom-up, instead of recursion that solves the same thing again and again.

Problem

The charging plan

A courier rides an electric scooter along a route of n km. There is a charging station at every kilometre, and the battery lasts for at most 2 km. So from every stop the courier goes on by 1 or 2 km to the next one. At every station where they stop, they pay its fee. The fees differ, and the app has to find the cheapest plan.

The first solution thinks backwards. The last stop is km n. Before it the courier was at km n − 1 or at km n − 2. So the cheapest to n is the fee at n plus the cheaper of the two: the cheapest to n − 1 and the cheapest to n − 2. That is recursion, as in the lesson "Recursion". The fees are in cents, and the counter says how many times the function was called:

static long calls = 0;

static int[] fees(int n) {
    int[] fee = new int[n + 1];
    for (int i = 1; i <= n; i++) {
        fee[i] = 40 + (i * 37) % 90;
    }
    return fee;
}

static int cheapest(int[] fee, int i) {
    calls++;
    if (i <= 1) {
        return fee[i];
    }
    int oneBack = cheapest(fee, i - 1);
    int twoBack = cheapest(fee, i - 2);
    return fee[i] + Math.min(oneBack, twoBack);
}

for (int km : new int[] {10, 30}) {
    calls = 0;
    int cost = cheapest(fees(km), km);
    System.out.println(km + " km: " + cost + " cents, " + calls + " calls");
}

Output

10 km: 381 cents, 177 calls
30 km: 1217 cents, 2692537 calls

The answer is right, but for 30 km the function was called 2,692,537 times. For 50 km it would be called 40,730,022,147 times: at a billion calls a second that is more than half a minute, and a courier route can be 100 km long.

The idea

The same question, asked millions of times

Why so many? Follow who asks what. The cheapest to km 30 asks for km 29 and km 28. Km 29 asks for 28 and 27. Km 28 is asked twice, and each time it is computed from scratch, together with everything under it. Further down the repeats pile up: km 27 is asked three times, km 26 five times.

The clean example of this is the Fibonacci numbers: each is the sum of the previous two, 0, 1, 1, 2, 3, 5, 8… The function has the same shape, the two smaller ones and a sum:

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

Output

fib(30) = 832040, 2692537 calls

The number of calls is the same to the last digit, because the call tree is the same. And the plan is just one of many places with this tree.

Such subproblems are called overlapping: the same smaller problem is needed by several bigger ones. In divide and conquer it is not like that. Merge sort splits the orders into two halves that share not a single order, and each piece is solved once. Here "the cheapest to km 28" is needed by km 29 and by km 30.

See it

The tree and the memory

The whole call tree for 6 km, then the same with memory. Watch which boxes repeat and what happens to them once their answer is remembered:

static int cheapestMemo(int[] fee, int i, int[] memo) {
    if (i <= 1) {
        return fee[i];
    }
    if (memo[i] != -1) {
        return memo[i];
    }
    int oneBack = cheapestMemo(fee, i - 1, memo);
    int twoBack = cheapestMemo(fee, i - 2, memo);
    memo[i] = fee[i] + Math.min(oneBack, twoBack);
    return memo[i];
}

Step by step, in words

1. Each box is one call cheapest(k): the cheapest way to reach km k. cheapest(6) asks for 5 and 4, and each of them asks for two smaller ones.
2. The tree stops at km 1 and 0, where the answer is the fee itself. For 6 km that is 25 calls.
3. The same questions over and over: cheapest(4) twice, cheapest(3) three times, cheapest(2) five times. The subproblems overlap.
4. With memory: the calls run in the same order, and the first time an answer is computed it goes into memo below.
5. The second time the answer is already in memo (green): the whole subtree under it never runs. 11 calls instead of 25.
6. A table, bottom up: best[0] and best[1] are the fees, and every next cell is built from the two before it. 5 cells, no recursion.
7. Each cell needs only the last two. Two variables slide along instead of the table: O(n) time and O(1) memory.

The idea

Remember the answer

The fix is not to compute the same thing twice. The first time you compute the cheapest to km k, write it down. The next time someone asks for k, return what you wrote.

static long calls = 0;

static int[] fees(int n) {
    int[] fee = new int[n + 1];
    for (int i = 1; i <= n; i++) {
        fee[i] = 40 + (i * 37) % 90;
    }
    return fee;
}

static int cheapestMemo(int[] fee, int i, int[] memo) {
    calls++;
    if (i <= 1) {
        return fee[i];
    }
    if (memo[i] != -1) {
        return memo[i];
    }
    int oneBack = cheapestMemo(fee, i - 1, memo);
    int twoBack = cheapestMemo(fee, i - 2, memo);
    memo[i] = fee[i] + Math.min(oneBack, twoBack);
    return memo[i];
}

int[] fee = fees(30);
int[] memo = new int[fee.length];
Arrays.fill(memo, -1);
int cost = cheapestMemo(fee, 30, memo);
System.out.println(cost + " cents, " + calls + " calls");

Output

1217 cents, 59 calls

The memory is an array with one place for every kilometre. -1 means "not computed yet": the fees are positive, so a real answer is never -1.

This is called memoization (remembering the results). The function is the same recursion, only with memory. 59 calls instead of 2,692,537: every kilometre is computed once, and the second question about it returns the ready answer.

A problem that is built from the answers of smaller problems, when those smaller ones repeat, is solved with dynamic programming: every subproblem is solved once and its answer is kept. The name is old and does not say much. Remember it as "remember and reuse".

Try it

Predict the output

The same function with memory, for a route of 8 km. How many times will it be called?

static long calls = 0;

static int[] fees(int n) {
    int[] fee = new int[n + 1];
    for (int i = 1; i <= n; i++) {
        fee[i] = 40 + (i * 37) % 90;
    }
    return fee;
}

static int cheapestMemo(int[] fee, int i, int[] memo) {
    calls++;
    if (i <= 1) {
        return fee[i];
    }
    if (memo[i] != -1) {
        return memo[i];
    }
    int oneBack = cheapestMemo(fee, i - 1, memo);
    int twoBack = cheapestMemo(fee, i - 2, memo);
    memo[i] = fee[i] + Math.min(oneBack, twoBack);
    return memo[i];
}

int[] fee = fees(8);
int[] memo = new int[fee.length];
Arrays.fill(memo, -1);
int cost = cheapestMemo(fee, 8, memo);
System.out.println(cost + " cents, " + calls + " calls");

Answer

331 cents, 67 calls

331 cents, 15 calls

331 cents, 8 calls

Check

The idea

Bottom up

The recursion with memory starts at km n and goes down until it reaches the small ones. You can also go the other way: start with the small ones and climb. The cheapest to km 0 and km 1 is the fee itself. From them follows km 2, then km 3, and so on up to n. When you reach a cell, the two under it are already done.

static int cheapestTable(int[] fee) {
    int n = fee.length - 1;
    int[] best = new int[n + 1];
    best[0] = fee[0];
    best[1] = fee[1];
    for (int i = 2; i <= n; i++) {
        int cheaper = Math.min(best[i - 1], best[i - 2]);
        best[i] = fee[i] + cheaper;
    }
    return best[n];
}

This is bottom-up dynamic programming, with a table. There is no recursion and no "is it computed yet" check: the order of the loop guarantees that everything needed is already in the table. There are n − 1 cells, with one piece of work per cell: O(n).

One more observation. Cell i only looks at i − 1 and i − 2. Everything before them is no longer needed. So the whole table can become two variables that slide forward:

static int cheapestPair(int[] fee) {
    int twoBack = fee[0];
    int oneBack = fee[1];
    for (int i = 2; i < fee.length; i++) {
        int here = fee[i] + Math.min(oneBack, twoBack);
        twoBack = oneBack;
        oneBack = here;
    }
    return oneBack;
}

int[] fee = fees(30);
System.out.println("table: " + cheapestTable(fee) + " cents");
System.out.println("two variables: " + cheapestPair(fee) + " cents");

Output

table: 1217 cents
two variables: 1217 cents

The time is still O(n), and the memory O(1): two numbers, however long the route.

See it

Measure it: no memory, with memory, with a table

Run the three on routes of 10, 20 and 30 km. We count the calls of the function, and for the table the cells. The recursion without memory is not run beyond 30 km: at 40 km it is 331,160,281 calls and the page would freeze.

• Recursion without memory O(2ⁿ)
• Recursion with memory O(n)
• Table, bottom up O(n)

Algorithm	n = 10	n = 20	n = 30
Recursion without memory	177	21,891	2,692,537
Recursion with memory	19	39	59
Table, bottom up	9	19	29

The code runs in your browser, in JavaScript. The number of operations is the same in every language, because the algorithm is the same. The time depends on the machine, so it is only for comparison. “≈” is an estimate from the curve: we do not run an n that big, so the page does not freeze.

static int cheapestMemo(int[] fee, int i, int[] memo) {
    if (i <= 1) {
        return fee[i];
    }
    if (memo[i] != -1) {
        return memo[i];
    }
    int oneBack = cheapestMemo(fee, i - 1, memo);
    int twoBack = cheapestMemo(fee, i - 2, memo);
    memo[i] = fee[i] + Math.min(oneBack, twoBack);
    return memo[i];
}

Every 10 km multiply the recursion without memory by about 123, while the other two grow by 20 and by 10. The Bench curve is labelled O(2ⁿ): it is exponential, with a base of about 1.6, the ratio between two neighbouring Fibonacci numbers.

More precisely, if you are curious

The same numbers in your language: the calls without memory, with memory, and the table cells for 10, 20 and 30 km.

static long calls = 0;
static long cells = 0;

static int[] fees(int n) {
    int[] fee = new int[n + 1];
    for (int i = 1; i <= n; i++) {
        fee[i] = 40 + (i * 37) % 90;
    }
    return fee;
}

static int cheapest(int[] fee, int i) {
    calls++;
    if (i <= 1) {
        return fee[i];
    }
    int oneBack = cheapest(fee, i - 1);
    int twoBack = cheapest(fee, i - 2);
    return fee[i] + Math.min(oneBack, twoBack);
}

static int cheapestMemo(int[] fee, int i, int[] memo) {
    calls++;
    if (i <= 1) {
        return fee[i];
    }
    if (memo[i] != -1) {
        return memo[i];
    }
    int oneBack = cheapestMemo(fee, i - 1, memo);
    int twoBack = cheapestMemo(fee, i - 2, memo);
    memo[i] = fee[i] + Math.min(oneBack, twoBack);
    return memo[i];
}

static int cheapestTable(int[] fee) {
    int n = fee.length - 1;
    int[] best = new int[n + 1];
    best[0] = fee[0];
    best[1] = fee[1];
    for (int i = 2; i <= n; i++) {
        cells++;
        int cheaper = Math.min(best[i - 1], best[i - 2]);
        best[i] = fee[i] + cheaper;
    }
    return best[n];
}

for (int km : new int[] {10, 20, 30}) {
    int[] fee = fees(km);
    calls = 0;
    cheapest(fee, km);
    long plain = calls;
    calls = 0;
    int[] memo = new int[fee.length];
    Arrays.fill(memo, -1);
    cheapestMemo(fee, km, memo);
    cells = 0;
    int cost = cheapestTable(fee);
    System.out.println(km + " km: " + plain + " / " + calls + " / " + cells + ", " + cost + " cents");
}

Output

10 km: 177 / 19 / 9, 381 cents
20 km: 21891 / 39 / 19, 822 cents
30 km: 2692537 / 59 / 29, 1217 cents

Try it

Find the bug

A colleague wrote the function with memory. The answer is right, but the counter shows the same as without memory:

int[] fee = fees(30);
int[] memo = new int[fee.length];
Arrays.fill(memo, -1);
int cost = cheapestMemo(fee, 30, memo);
System.out.println(cost + " cents, " + calls + " calls");

Output

1217 cents, 2692537 calls

Which line has the bug?

Pick the line with the bug.

1static int cheapestMemo(int[] fee, int i, int[] memo) {2 if (i <= 1) {3 return fee[i];4 }5 if (memo[i] != -1) {6 return memo[i];7 }8 int oneBack = cheapestMemo(fee, i - 1, memo);9 int twoBack = cheapestMemo(fee, i - 2, memo);10 return fee[i] + Math.min(oneBack, twoBack);11}

Check

Try it

Fill in

Cell i in the table is the fee at km i plus the cheaper of the two places you can come from. What is the second one?

static int cheapestTable(int[] fee) {
    int n = fee.length - 1;
    int[] best = new int[n + 1];
    best[0] = fee[0];
    best[1] = fee[1];
    for (int i = 2; i <= n; i++) {
        int cheaper = Math.min(best[i - 1], );
        best[i] = fee[i] + cheaper;
    }
    return best[n];
}

Check

Exercise

The fees from the input

Solve it in your editor.

The cheapest plan. Read the station fees from km 1 to km n (in cents, separated by spaces) and print the cheapest plan. Use cheapestPair from the lesson.

Input

77 114 61 98 45 82

Output

Cheapest: 265 cents

More tasks

• Which stations. Print the kilometres where the courier stops, too. Hint: next to the table, keep where each cell came from (i − 1 or i − 2), then walk back from n.
• How many plans. Count all plans, whatever they cost. How many are there for 30 km? Compare the numbers with the Fibonacci numbers. (For 30 km there are 1,346,269.)
• A better battery. The new scooter lasts 3 km. How does the formula change, and how many variables do you need instead of two?

More precisely

The depth and built-in memory

Memory cuts the work, but the recursion is still recursion.

More precisely, if you are curious

How deep it goes. The recursion with memory first goes down the chain n, n − 1, … 1, and only then starts storing. The call stack is n frames, as in the lesson on the stack. The table does the same work in a loop, and the stack does not grow, as in from recursion to a loop.

static int[] fees(int n) {
    int[] fee = new int[n + 1];
    for (int i = 1; i <= n; i++) {
        fee[i] = 40 + (i * 37) % 90;
    }
    return fee;
}

static int cheapestMemo(int[] fee, int i, int[] memo) {
    if (i <= 1) {
        return fee[i];
    }
    if (memo[i] != -1) {
        return memo[i];
    }
    int oneBack = cheapestMemo(fee, i - 1, memo);
    int twoBack = cheapestMemo(fee, i - 2, memo);
    memo[i] = fee[i] + Math.min(oneBack, twoBack);
    return memo[i];
}

static int cheapestTable(int[] fee) {
    int n = fee.length - 1;
    int[] best = new int[n + 1];
    best[0] = fee[0];
    best[1] = fee[1];
    for (int i = 2; i <= n; i++) {
        int cheaper = Math.min(best[i - 1], best[i - 2]);
        best[i] = fee[i] + cheaper;
    }
    return best[n];
}

int[] fee = fees(1000000);
try {
    int[] memo = new int[fee.length];
    Arrays.fill(memo, -1);
    cheapestMemo(fee, 1000000, memo);
} catch (StackOverflowError e) {
    System.out.println("cheapestMemo: StackOverflowError");
}
System.out.println("cheapestTable: " + cheapestTable(fee));

Output

cheapestMemo: StackOverflowError
cheapestTable: 38866659

Java and JavaScript have no limit on the number of levels, but the stack is about 1 MB, and 100,000 nested calls do not fit. In Python the limit is 1000 levels.

Memory built into the language. In Java it is tempting to write the memory as memo.computeIfAbsent(i, k -> fee[k] + Math.min(...)) with the recursion inside. Do not do it with HashMap: a recursive call that changes the same map during computeIfAbsent throws ConcurrentModificationException (since Java 9). An array, or containsKey + put, is safe.

Top down or bottom up. Both ways solve the same subproblems. With memory it computes only those it actually reaches, and you write it straight from the naive recursion. With a table there is no recursion and it can often be shrunk as here. If the subproblems are many and the answer needs few of them, memory wins. If nearly all are needed, the table is faster and does not risk the stack.

Test

Check yourself

1. Why does the recursion without memory make 2.7 million calls for 30 km, and only 59 with memory?

With memory the function skips the kilometres it does not needWithout memory the same subproblems (the cheapest to km 5, to km 4…) are solved again every time someone asks for themMemory makes every call faster

2. How does dynamic programming differ from divide and conquer in merge sort?

Merge sort uses a table and dynamic programming does notDynamic programming always splits in halfIn merge sort the halves do not overlap and each subproblem is solved once without memory; here the subproblems repeat and it pays to remember them

3. The table for n km is filled from best[2] to best[n]. How much memory does the two-variable version need?

O(log n)O(1): only the last two valuesO(n): the whole table

4. A function with memory checks the memory but never writes to it. What happens?

The answer comes out wrongThe answer is right, but the calls are as many as without memoryThe function never stops

5. Why does the recursion with memory fail in Python for 5000 km, while the table works?

Python memory is not enough for 5000 numbersThe table uses smaller numbersWith memory the first call goes 5000 levels down before it stores anything, and the Python limit is 1000 levels; the table is a loop without recursion

Check

Start the lesson over

Related lessons

• Builds on: Merge sort and "divide and conquer" · The call stack from the inside · From recursion to a loop · Divide and conquer and the recursion tree
• Continues in: The coin change problem · The knapsack problem · The longest common subsequence and diff · How to recognise a DP task
• Tasks on this topic: Dynamic programming