Python Arena
Start learning
Step 2 of 6

Bottom-up tables

Memoization is top-down: the first call asks the big question, the recursion works its way down to the small ones, and each answer is saved as it comes back up. Bottom-up DP, also called tabulation, turns this around. A loop fills a list, smallest questions first, going in an order where every answer an entry needs has been filled in before the loop gets to it. With no recursion there's no recursion limit, and a loop that indexes a list is faster than calls and dict lookups.

Climbing stairs

You climb a staircase one or two steps at a time. In how many ways can you climb n steps? Think about the last move: it was one step, from step n - 1, or two steps, from step n - 2. So ways[n] = ways[n - 1] + ways[n - 2]. Standing at the bottom counts as the one way to climb 0 steps (no moves at all), and a single step can only be climbed one way. Fill the list from there up:

def stairs(n):
    ways = [0] * (n + 1)
    ways[0] = 1
    for i in range(1, n + 1):
        ways[i] = ways[i - 1]
        if i >= 2:
            ways[i] += ways[i - 2]
    return ways


print(stairs(10))
Output
[1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89]

The list has n + 1 places, for 0 to n steps. Leaving out the + 1 is the classic off-by-one: ways[n] then stops with an IndexError. Negative indexes are the other trap: at i = 1, ways[i - 2] is ways[-1], the last item of the list, and Python hands it over without an error. The if i >= 2 keeps the loop from reading it. No call waits on another, so the recursion limit is gone: the loop goes as high as you like. The cost is O(n) additions and O(n) entries, but that counts each entry as O(1), which is true only while the numbers stay small. These counts grow by about one digit every five steps, and a sum of numbers with thousands of digits is slow to work out and takes room to keep: "Huge answers" below shows the fix.

Tilings

The same thinking counts tilings. In how many ways can 1 × 2 dominoes cover a strip 2 high and n long? Look at the left end. Either one domino stands upright there, covering the first column and leaving a strip n - 1 long, or two dominoes lie flat, one above the other, covering two columns and leaving n - 2:

upright:  |...      flat:  ==..
          |...             ==..

So tilings(n) = tilings(n - 1) + tilings(n - 2), with one tiling of the empty strip and one of a strip 1 long: the stairs again. That's the heart of DP: say what an entry means, then find how it's built from smaller entries by looking at the first or last choice.

Keeping only the last values

ways[i] reads only the two entries before it, and once they're used, the older ones are never read again. So two variables are enough, and the memory drops to O(1):

def tilings(n):
    before, current = 1, 1          # strips 0 and 1 long
    for _ in range(n - 1):
        before, current = current, before + current
    return current


print([tilings(n) for n in range(1, 11)])
Output
[1, 2, 3, 5, 8, 13, 21, 34, 55, 89]

The two variables must change together. before, current = current, before + current works out both values on the right from the old ones before it assigns either. Written as two lines, before = current and then current = before + current, the second line already sees the new before, so it adds current to itself, and the numbers just double: 2, 4, 8, 16.

Huge answers

Counts grow fast: the ways to climb 1,000 steps have 209 digits. Python's whole numbers never overflow, but adding numbers of thousands of digits is slower than adding small ones, and Python won't even turn a number of more than 4,300 digits into text:

a, b = 0, 1
for _ in range(30_000):
    a, b = b, a + b
print(a)
Python stops with
Traceback (most recent call last):
  File "main.py", line 4, in <module>
    print(a)
    ~~~~~^^^
ValueError: Exceeds the limit (4300 digits) for integer string conversion; use sys.set_int_max_str_digits() to increase the limit

So counting problems usually ask for the answer modulo 1,000,000,007, the remainder after dividing by that prime. Take % MOD after every addition: (a + b) % m is the same as (a % m + b % m) % m, so the remainders add up like the numbers do, and every entry stays below 1,000,000,007.

Your task

Challenge 1 of 3

A strip 2 high and n long can be tiled with 2 × 2 squares as well as 1 × 2 dominoes. At the left end there are now three choices: an upright domino (leaving n - 1), two flat dominoes (leaving n - 2) or a square (leaving n - 2). So tiles(n) = tiles(n - 1) + 2 * tiles(n - 2), and tiles(0) and tiles(1) are both 1.

This tiles keeps only the last two values, but from n = 3 on its answers are wrong. Fix it, so that print([tiles(n) for n in range(6)]) prints:

[1, 1, 3, 5, 11, 21]

Challenge 2

On a steep staircase with long legs, every move takes you up 2 or 3 steps, never just 1. Write stairs(n): the number of ways to climb exactly n steps, modulo MOD. There's 1 way to climb 0 steps, none to climb 1, and 2 ways to climb 5 (2 + 3 and 3 + 2). The tests go up to 200,000 steps, where plain recursion never ends and memoized recursion would wait on about 100,000 calls at once, far past Python's limit, so fill a table from the bottom up.

For example, print(stairs(5), stairs(10)) prints:

2 7

Challenge 3

A temp worker is offered a shift on each of the coming days, and pay[i] is what the shift on day i pays, counting the days from 0. The rule: never two days in a row. Write best_total(pay), the most the worker can earn. pay may be empty: then the answer is 0.

Look at the last day. Either the worker skips it and earns the best total of the days before it, or works it and earns its pay plus the best total of all the days but the last two. The tests have 300,000 days, so fill the answers in from the first day on. Two variables are enough: the best total up to the day before, and up to the day before that.

For example, best_total([5, 1, 2, 9, 3]) returns 14, working the first and the fourth day:

14
Previous: Memoization Next: Coin change