Overlapping subproblems

Dynamic programming, or DP, solves a problem from the answers to smaller problems of the same kind, and it saves each of those answers so that no smaller problem is solved twice. This lesson shows when that works, and how to describe a DP clearly before writing any code.

A problem made of smaller ones

GRDY-5 showed that greedy change fails with the coins 1, 3 and 4: for 6 it gives 4 + 1 + 1, but 3 + 3 uses fewer coins. To find the true fewest number of coins, think about the first coin. It is 1, 3 or 4. Whatever it is, the rest of the coins must make the amount that is left, and they should do it with as few coins as possible.

Write f(x) for the fewest coins that make the amount x. Then f(0) = 0, and for x > 0, f(x) is 1 plus the smallest of the values f(x − c), over every coin c ≤ x.

Why is this right? Take a best way to make x, and remove its first coin c. The coins that are left make x − c. They must be a best way to make x − c: if there were a way with fewer coins, putting c in front of it would make x with fewer coins than the best way, which is impossible. So the best for x is one coin plus the best for some x − c, and the rule tries every c.

def f(x, coins=(1, 3, 4)):
    if x == 0:
        return 0
    return 1 + min(f(x - c, coins) for c in coins if c <= x)

This is correct, and very slow. The figure shows why.

The same question again

A subproblem is a smaller problem of the same kind, such as f(2) inside f(5). In the first version of the figure, the plain recursion asks for f(1) four times and works it out from scratch each time. When the same subproblems come up again and again like this, they are called overlapping subproblems.

The number of calls grows by about 1.38 times for every 1 added to the amount: 15 calls for 5, 168 for 10, 2,550,408 for 30. But the number of different questions is only x + 1: the amounts 0 to x. The second version of the figure asks each question once, smallest first, and writes the answer in a row. Every answer it needs is already in the row. That is dynamic programming.

For the coins that is (x + 1) × k steps for k coin values, or O(x · k). For an amount of 30 and three coins, about 93 steps instead of 2.5 million calls.

Two properties

DP works when a problem has two properties.

1. Optimal substructure. A best answer to the problem is made of best answers to subproblems. The argument above, with the first coin removed, proves this for the coins. It is the step that most needs a proof, because it is not always true.
2. Overlapping subproblems. The same subproblems are needed many times. Without this, saving answers does not help.

An example without the first property: the longest route between two stations that never visits a station twice. The longest route from A to B and the longest route from B to C may pass through the same station, so joining them can break the rule about visiting a station twice. A best route is not made of best smaller routes. No DP over the stations works here, and no fast method is known at all (HARD).

An example without the second property: merge sort. Its two halves are different parts of the list, and no part is ever sorted twice. Plain recursion is already efficient, and a store of answers would only use memory. This is the line between divide and conquer (DVCQ) and DP.

Counting problems, such as the number of ways to make an amount, need a property of the same kind: the ways split into groups that do not overlap and leave nothing out (one group for each first coin, say), and each group is counted by a subproblem. Then the count is a sum of smaller counts.

States and rules

Every DP in this station is described in the same five steps. Write them down before writing code.

1. State. Say in words what one subproblem is: “f(x) = the fewest coins that make x”. A vague state is the most common cause of a wrong DP.
2. Rule. How a state’s answer comes from smaller states. Usually: look at the first or the last choice, and try every possibility. This rule is also called the recurrence.
3. Base cases. The smallest states, answered directly: f(0) = 0.
4. Order. Each state must use only states that are “smaller” in some fixed sense, so that the rule never goes round in a circle. Draw each state as a point, with an arrow to each state it uses. The arrows must never form a loop. Such a picture is called a DAG, a directed acyclic graph: directed because the arrows have a direction, acyclic because there are no loops.
5. Answer. Which state, or which mix of states, is the answer: here f(amount).

The cost follows from steps 1 and 2: count the states and the work in the rule. Space is the number of states kept, which lesson 3 often cuts down.

DP, greedy, divide and conquer

So DP is a careful search of every choice, made fast by sharing. When a greedy rule can be proved, it is usually faster still; when it cannot, DP is the next tool to try. The next two lessons show the two ways to share answers: keep the recursion and remember answers (lesson 2), or fill a table with loops (lesson 3).

Now try DYNP-P1, Shapes of a search tree.