Dynamic programming and the frog problem
Dynamic programming (DP) solves a problem by solving smaller versions of the same problem first. Each smaller answer is worked out once and stored in a table, and the larger answers are built from the stored ones. The word "programming" in the name means planning by filling in a table, not writing code. The method is easiest to follow on an example, so we start with one.
There are stones in a row, and stone has height . A frog starts on the first stone and wants to reach the last one. From any stone it can jump to the next stone or to the one after that, and a jump between stones of heights and costs .
The first input line holds and the second the heights. Print the minimum total cost of reaching the last stone.
Constraints
Sample 1 · Input
4 10 30 40 20
Output
30
Sample 2 · Input
2 10 10
Output
0
Sample 3 · Input
6 30 10 60 10 60 50
Output
40
A frog crosses a row of stones. Each jump takes it to the next stone or to the one after that, and a jump costs the difference in height between the two stones. We want the cheapest way to get from the first stone to the last. In the first sample the heights are 10, 30, 40 and 20. We'll number the stones from 0, the way list positions are numbered, so the frog starts on stone 0 and has to reach stone 3. It has three routes:
- costs .
- costs .
- costs .
The cheapest costs 30, which is the expected output. A program could find the answer the same way, by listing every route and keeping the cheapest, but the number of routes grows too fast. Every route to a stone comes from one of the two stones before it, so a stone's count of routes is the sum of those two stones' counts. Stones 0 and 1 have one route each, and from there the counts run 1, 1, 2, 3, 5, 8, 13: the Fibonacci numbers. Fifty stones have 12,586,269,025 routes to the last one. At the problem's limit of stones, the number of routes has 20,899 digits.
Build the transition from the last jump
Listing routes repeats work: every route through stone 2 starts with a route to stone 2, whose cost is added up again for every way of continuing from stone 2. One question per stone is enough: what is the cheapest cost of reaching stone ? Call the answer dp[i]. The last jump of a route to stone starts on stone or stone . If it starts on stone , the cheapest such route reaches that stone for dp[i - 1] and then pays for the jump, where is the height of stone . The same goes for stone . That gives one candidate for each possible last jump, and dp[i] is the smaller:
A rule like this is called a transition: it computes the value for one stone from the values for earlier stones. It uses only the cheapest way of reaching stone and forgets the others, because the jumps still ahead do not depend on how the frog got there. Two routes that reach stone with different totals face the same jumps at the same prices, so whatever the frog does next adds the same amount to either, and the more expensive arrival cannot finish cheaper.
Two stones need separate treatment. The frog starts on stone 0, so dp[0] is 0, and stone 1 can only be reached from stone 0, so dp[1] is . Every later entry reads the two entries before it, so if we fill the table from left to right, both are ready by the time we need them.
Here is the table for the sample, filled from left to right. dp[0] is 0 and dp[1] is 20. Stone 2 compares arriving from stone 1 with arriving from stone 0, and stone 3 compares arriving from stone 2 with arriving from stone 1:
The finished table is [0, 20, 30, 30]. Its last entry, 30, is the answer, the cost of the cheapest route we listed. This time it took at most one comparison per stone, and we never wrote out a whole route.
Definition
A dynamic programming solution comes down to two choices: the states, and the transition that computes each state from the others.
- A state is one of the smaller questions, such as "the cheapest cost of reaching stone 3". The table stores one value per state.
- A transition is the rule that computes a state's value from the values of other states. Textbooks also call it a recurrence. To find one, ask what the last step of an answer can be. Each possible last step gives one candidate for the value, as the frog's two last jumps did, and the transition combines the candidates.
Two smaller things complete the solution. The base cases are the states whose values are written down directly, without a transition: here dp[0] and dp[1]. The evaluation order is the order in which the table is filled, and it must store every value before a transition reads it: here, left to right.
Fill the table with a loop
The program fills the table in the same order. For each stone it first takes the jump from stone , and from stone 2 onward it compares that with the jump from stone . That way stone 1 needs no case of its own, and the program never reads an entry before dp[0].
def min_cost(h):
n = len(h)
dp = [0] * n
for i in range(1, n):
dp[i] = dp[i - 1] + abs(h[i] - h[i - 1])
if i >= 2:
dp[i] = min(dp[i], dp[i - 2] + abs(h[i] - h[i - 2]))
return dp[n - 1]
n = int(input())
h = list(map(int, input().split()))
print(min_cost(h))On the first sample the program prints 30.
Each stone takes at most two additions and one comparison, so stones need a few hundred thousand steps. That is time and one stored number per stone.
Worked example
Predict each entry yourself
The trace fills the same table one stone at a time. Switch on Predict the next step to work out each entry before it appears. The other presets include a tall middle stone that is cheaper to jump over, and a row with only one stone.
Optional practice. Try an answer or keep stepping; predictions do not award XP or solve credit.
dp[i] means the minimum cost to reach stone i. Stone 0 costs zero because the frog starts there.
Change the example input
Current result: 30
Rebuild the route with parent links
The table gives the cost of the cheapest route but not the route. Frog 1 does not ask for it, but many problems do, and the method is the same for all of them: while filling the table, remember which choice each entry kept, then follow those choices back from the answer.
For the frog, the choice is the stone the last jump came from. Call it the parent of stone and store it in parent[i]. In the first sample, stone 3 kept the jump from stone 1, and stone 1 can only come from stone 0. Walking back from stone 3 visits 3, 1 and 0, so the route is , the green one in the figure.
n = int(input())
h = list(map(int, input().split()))
dp = [0] * n
parent = [-1] * n
for i in range(1, n):
dp[i] = dp[i - 1] + abs(h[i] - h[i - 1])
parent[i] = i - 1
if i >= 2 and dp[i - 2] + abs(h[i] - h[i - 2]) < dp[i]:
dp[i] = dp[i - 2] + abs(h[i] - h[i - 2])
parent[i] = i - 2
route = []
i = n - 1
while i != -1:
route.append(i)
i = parent[i]
route.reverse()
print(dp[n - 1])
print(*route)The walk starts on the last stone and follows parents until it passes stone 0, whose parent is . That collects the route backwards, so the program reverses it before printing. When the two candidates are equal, as they are for stone 2 of the first sample, either stone would do as the parent, and the listing keeps stone .
The widget fills the table for the third sample, heights 30, 10, 60, 10, 60 and 50, which is also the listing's input. At each step the green entry is the parent that the new entry keeps, and on the last step the widget walks back from the answer and marks the route.
The finished table is [0, 20, 30, 20, 30, 40]. The walk back visits stones 5, 4, 2 and 0, so the route is , with cost . You can edit the heights. If the last one changes from 50 to 10, the cheapest route moves to stones 1, 3 and 5 and costs 20.
Count with the same table
The frog's table kept a minimum. The same kind of table can also count, and you have already seen one do it. When we counted the frog's routes at the start of the lesson, each stone's count was the sum of the counts for the two stones before it. The next problem asks for that count, with steps in place of stones.
A staircase has steps, and each move climbs 1 or 2 of them. Return the number of distinct ways to reach the top.
Constraints
Sample 1 · Input
n = 2
Output
2
Sample 2 · Input
n = 3
Output
3
For the three ways are , and . Let ways[i] be the number of ways to reach step , where step 0 is the floor. The last move onto step climbed 1 step or 2, so it started on step or on step :
Where the frog compared its two candidates and kept the smaller, a count adds them. The sum is right because every way of reaching step ends with exactly one of the two moves, so no way is counted twice and none is left out.
The base cases are ways[0] = 1 and ways[1] = 1. The first can look odd, but there is exactly one way to be on the floor, which is to make no move. With that value the transition gives ways[2] = 1 + 1 = 2, as it should.
def climb_stairs(n):
ways = [1] * (n + 1)
for i in range(2, n + 1):
ways[i] = ways[i - 1] + ways[i - 2]
return ways[n]
print(climb_stairs(2), climb_stairs(3), climb_stairs(45))The counts grow quickly. For , the largest input the problem allows, the answer is 1,836,311,903, just under the largest 32-bit signed integer, 2,147,483,647. For it would be 2,971,215,073. Counting problems with larger inputs ask for the answer modulo a prime to keep the numbers small, and the Deeper read below works through one.
Each entry reads only the two before it, so the loop could keep two variables and no table. That saves memory when the final number is all you need, and the House Robber program later in this chapter is written that way. Rebuilding a route with parent links needs the whole table.
Deeper read: count large totals modulo a prime
Count the ways to make the sum by throwing a die one or more times, where each throw shows 1 to 6 and the order of the throws matters. For the ways are , , and .
The input is one integer . Print the count modulo .
Constraints
Sample · Input
3
Output
4
This is Climbing Stairs with six possible last moves where there were two. Let ways[x] be the number of ways to make the sum . The last throw shows a face from 1 to 6, and the throws before it add up to , so ways[x] is the sum of the entries for those smaller sums, up to six of them. As with the stairs, ways[0] = 1 counts the empty sequence of throws:
The exact counts are huge. For there are already 389,043,663,364,337 ways. Python integers never overflow, but at the count has almost 300,000 digits, and millions of additions of numbers that long are far too slow.
That is why the problem asks for the count modulo . The remainder of a sum depends only on the remainders of its parts, so the program can take the remainder after every addition. Every stored value then stays below , and the final remainder is still the right one.
MOD = 10**9 + 7
n = int(input())
ways = [1] + [0] * n
for x in range(1, n + 1):
for face in range(1, min(6, x) + 1):
ways[x] = (ways[x] + ways[x - face]) % MOD
print(ways[n])Memoization and tabulation
Every table so far was filled by a loop that starts at the smallest state and works up. A transition can also be followed in the other direction: start from the state you want and let recursive calls reach the states it reads. Here is the stairs transition written that way:
def ways_slow(n):
if n <= 1:
return 1
return ways_slow(n - 1) + ways_slow(n - 2)
print(ways_slow(3))The function is correct and far too slow, because it computes the same values over and over. ways_slow(5) calls ways_slow(4) once, ways_slow(3) twice, ways_slow(2) three times and ways_slow(1) five times, and each of those calls computes its value from scratch and makes every call beneath it again. The counts 1, 2, 3 and 5 are the Fibonacci numbers again.
ways_slow(5) makes, with standing for ways_slow(n). Each grey call repeats one made earlier, along with every call below it.The number of calls can be worked out exactly. Read the call tree as a tree of additions: a base-case call returns 1 and every other call adds what its two calls return, so ways_slow(5), which returns 8, makes 8 base-case calls. Say it also makes calls that are not base cases. Each of those makes exactly two calls, and every call except the first is made by one of them, so the total is . The total is also , so and there are 15 calls. In general the function makes calls. For that is 3,672,623,805 calls to compute 46 different values.
Memoization removes the repetition. The function stores each answer the first time it computes it and returns the stored answer on every later call. Each value is then computed once: in the figure, the top call of each grey subtree becomes a single lookup in the memo column, and the grey calls below it are never made.
The @cache decorator from functools does the storing. It keeps a dictionary from the function's arguments to its results.
@cache
def ways_memo(n):
if n <= 1:
return 1
return ways_memo(n - 1) + ways_memo(n - 2)
print(ways_memo(45))If you trace the memoized calls, you find that they finish in increasing order of : after the base cases, ways_memo(2) finishes first, then ways_memo(3), and so on up to ways_memo(45). The Climbing Stairs loop fills the table in that same order without any recursion. The two compute the same values from the same transition, and both are dynamic programming. The recursion is called top-down, because it starts from the answer you want. The loop is called bottom-up, or tabulation.
Try every possible last choice
The frog always had two possible last jumps, and the stairs two last moves. In the next problem, the number of candidates depends on the input.
coins lists coin values, with an unlimited supply of each. Return the fewest coins that add up to exactly amount, or -1 if no combination does.
Constraints
-
coins.length -
coins[i] -
amount
Sample 1 · Input
coins = [1,2,5], amount = 11
Output
3
Sample 2 · Input
coins = [2], amount = 3
Output
-1
Sample 3 · Input
coins = [1], amount = 0
Output
0
A first idea is to keep paying with the largest coin that fits. A rule like this is called greedy: it makes each choice on the spot, without working out what that choice leaves for later. It works on the first sample, where it pays , but not in general. With the coins 1, 4 and 6 and the amount 8 it takes the 6, which leaves 2 to pay with two 1s, so it pays , three coins, when needs only two.
So we build a table. The state is an amount: dp[x] is the fewest coins that add up to exactly . For the transition, look at the last coin of a payment. If it is worth , the coins before it add up to , and the fewest coins that can do that is dp[x - c]. Any coin worth at most can be the last one, so we try them all and keep the best:
The base case is dp[0] = 0, since the amount 0 needs no coins. Every coin is worth at least 1, so dp[x] only reads entries to its left, and filling the amounts in increasing order has them all ready. The widget does that for the coins 1, 4 and 6 up to the amount 8. You can change the coins and the amount.
At the amount 8 the table compares all three possible last coins, where the largest-coin rule only ever looked at the 6:
One case is still missing. Some amounts cannot be paid at all, such as 3 when the only coin is 2, and the problem wants for those. The program starts every entry except dp[0] at infinity, which here means "no payment found yet". An entry stays at infinity when every entry it reads is at infinity too, because one coin more than an impossible payment is still impossible.
def coin_change(coins, amount):
INF = float("inf")
dp = [0] + [INF] * amount
for x in range(1, amount + 1):
for c in coins:
if c <= x:
dp[x] = min(dp[x], dp[x - c] + 1)
return -1 if dp[amount] == INF else dp[amount]
print(coin_change([1, 2, 5], 11), coin_change([2], 3), coin_change([1], 0))The table has one entry per amount and each entry tries every coin, so the work is the number of states times the number of candidates per state. At the problem's limits that is steps. The same method gives the running time of any of these tables: add up the work for every state, counting each stored value a state reads as one step, since it is already in the table.
Time and space of these tables
- Frog and Climbing Stairs
time - states with two candidates each. The table takes space, or two variables when only the final value is needed.
- Plain recursion for the stairs
calls - Every repeated state is computed again. With a memo each of the states is computed once.
- Dice Combinations
time - states with up to six candidates each.
- Coin Change
time, space - One state per amount up to , each trying all coins.
Common mistakes
Letting stone 1 read
dp[i - 2]too.- Where it breaks
- In Python,
dp[-1]reads the last entry and raises no error. On the sample[10, 30, 40, 20], stone 1 reads that untouched entry as 0, stores where it should store 20, and the program prints20where the answer is30. In C++ the same read is outside the vector, and anything may happen. - The fix
- Read
dp[i - 2]only when .
Filling the table in an order where the entries it reads are not ready.
- Where it breaks
- Coin Change with the coins
[1, 4, 6]and the amount 8, looping the amounts from 8 down to 1, readsdp[7],dp[4]anddp[2]while they are still at infinity and returns-1where the answer is2. - The fix
- Order the loop so that every entry a transition reads is filled earlier. Here that means amounts upward.
Starting a count at
ways[0] = 0.- Where it breaks
- Climbing Stairs with
ways[0] = 0andways[1] = 1givesways[2] = 1andways[3] = 2, where the answers are2and3. Every climb that starts with a move of 2 from the floor goes uncounted. - The fix
- Give the empty sequence of moves its one way:
ways[0] = 1.
Recall Frog 2, the next problem in the same AtCoder contest, lets the frog jump up to `K` stones ahead. How does the transition change, and how much work is the table?
The last jump into stone can now start on any of the stones before it, so dp[i] is the smallest of up to candidates, dp[j] plus for each from to that exists. The states stay as they were, and dp[0] = 0 is the only base case it needs. It is the frog's table with Coin Change's loop over candidates.
There are states with up to candidates each. At the limits of Frog 2, and , that is steps.
Key terms
| Term | Meaning |
|---|---|
| state | One of the smaller questions, such as the cheapest cost of reaching stone . The table stores one value per state. |
| transition | The rule that computes a state's value from the values of other states. |
| base case | A state whose value is written down directly, without a transition. |
| evaluation order | The order in which the table is filled. Every value a transition reads must already be stored. |
| candidate | One possible value for a state, from one possible last step. The transition combines the candidates. |
| parent | The earlier state whose candidate an entry kept. Following parents back from the answer rebuilds the choices. |
| memoization (top-down) | A recursive function that stores each answer the first time it computes it. |
| tabulation (bottom-up) | A loop that fills the table in evaluation order. |
