Recursion with the answers remembered

The four-step ladder that every problem in this unit climbs, on a recurrence you have already met.

A problem you have already seen

In Unit 10 you generated every binary string of a given length with no two adjacent ones, and the counts for length 3 and length 10 were 5 and 144. Those are Fibonacci numbers, and that lesson noted that the counting version is a dynamic programming exercise rather than a search.

Here it is. Counting them without generating them is the whole point: generation is exponential and counting is linear.

Key idea

Step one: correct and slow

Write the recursion that answers the question directly, ignoring efficiency entirely. Nothing else works until this exists, because the recurrence you are about to optimize is the one this contains.

Ask: what choices are available at this position, and what does each leave behind? Here, either place a zero and continue, or place a one and be forced to place a zero next.

1def count_slow(length, last_was_one=False):2    if length == 0:3        return 1                       # one complete string4    total = count_slow(length - 1, False)          # place a zero5    if not last_was_one:6        total += count_slow(length - 1, True)      # place a one7    return total8 9print(count_slow(3), count_slow(10))

Why it works

Step two: remember what you computed

The recursion above recomputes the same pair of arguments many times. Store each result the first time and read it thereafter.

The key is the full set of arguments, since those are what determine the answer. Getting the key wrong, by leaving out a parameter the answer depends on, produces a memo that returns confidently wrong results, and it is the most damaging error in this unit.

1def count_memo(length, last_was_one=False, seen=None):2    if seen is None:3        seen = {}4    if length == 0:5        return 16    key = (length, last_was_one)                  # every argument, none left out7    if key in seen:8        return seen[key]9    total = count_memo(length - 1, False, seen)10    if not last_was_one:11        total += count_memo(length - 1, True, seen)12    seen[key] = total13    return total14 15print(count_memo(3), count_memo(40))

Key idea

Step three: turn it into a table

Memoized recursion is often the right place to stop, and it is easy to write and easy to explain. A table replaces the recursion with a loop, which avoids recursion-depth limits and is usually a little faster.

To convert, ask what the subproblems are indexed by and in what order they can be filled so that everything a cell needs is already present. Here the index is the length and the order is small to large.

1def count_table(length):2    if length == 0:3        return 14    ending_zero = [0] * (length + 1)     # strings of this length ending in 05    ending_one = [0] * (length + 1)6    ending_zero[1], ending_one[1] = 1, 17 8    for n in range(2, length + 1):9        ending_zero[n] = ending_zero[n - 1] + ending_one[n - 1]10        ending_one[n] = ending_zero[n - 1]        # a one must follow a zero11    return ending_zero[length] + ending_one[length]12 13print(count_table(3), count_table(10))

Key idea

Step four: keep only what the table uses

Look at which cells the loop actually reads. Here every line reads only the previous index, so the whole array is unnecessary and two variables suffice.

This is the last step and it is optional. Do it when space matters or when an interviewer asks. Doing it first, before the table is correct, is how people end up with two variables and no idea which is which.

1def count_rolling(length):2    if length == 0:3        return 14    zero, one = 1, 15    for _ in range(2, length + 1):6        zero, one = zero + one, zero7    return zero + one8 9print(count_rolling(3), count_rolling(10), count_rolling(40))

Predict the output· 5 min

Predict the output: a memo key that loses a parameter

This memoizes on the length alone, ignoring the other parameter the answer depends on. Type the two values it prints.

Python

1def count_bad(length, last_was_one=False, seen=None):2    if seen is None:3        seen = {}4    if length == 0:5        return 16    if length in seen:7        return seen[length]8    total = count_bad(length - 1, False, seen)9    if not last_was_one:10        total += count_bad(length - 1, True, seen)11    seen[length] = total12    return total13 14def count_good(length, last_was_one=False, seen=None):15    if seen is None:16        seen = {}17    if length == 0:18        return 119    key = (length, last_was_one)20    if key in seen:21        return seen[key]22    total = count_good(length - 1, False, seen)23    if not last_was_one:24        total += count_good(length - 1, True, seen)25    seen[key] = total26    return total27 28print(count_bad(10), count_good(10))

Printed output

Code lab· 30 min

Climb the ladder

One recurrence, three ways. ways_slow counts sequences of 1s and 3s summing to n, by plain recursion. ways_memo does the same with memory. ways_rolling does it with a fixed number of variables. All three must agree.

solution.py

Tests

print([ways_slow(n) for n in range(7)])print([ways_memo(n) for n in range(7)])print([ways_rolling(n) for n in range(7)])print(ways_memo(30) == ways_rolling(30), ways_rolling(30))

Output

Run tests to see output.

Problem· 18 min

Climbing Stairs

Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.

Problem· 20 min

Min Cost Climbing Stairs

Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.

A problem you have already seen

Here it is. Counting them without generating them is the whole point: generation is exponential and counting is linear.

1def count_memo(length, last_was_one=False, seen=None):2 if seen is None:3 seen = {}4 if length == 0:5 return 16 key = (length, last_was_one) # every argument, none left out7 if key in seen:8 return seen[key]9 total = count_memo(length - 1, False, seen)10 if not last_was_one:11 total += count_memo(length - 1, True, seen)12 seen[key] = total13 return total14 15print(count_memo(3), count_memo(40))

1def count_table(length):2 if length == 0:3 return 14 ending_zero = [0] * (length + 1) # strings of this length ending in 05 ending_one = [0] * (length + 1)6 ending_zero[1], ending_one[1] = 1, 17 8 for n in range(2, length + 1):9 ending_zero[n] = ending_zero[n - 1] + ending_one[n - 1]10 ending_one[n] = ending_zero[n - 1] # a one must follow a zero11 return ending_zero[length] + ending_one[length]12 13print(count_table(3), count_table(10))

1def count_bad(length, last_was_one=False, seen=None):2 if seen is None:3 seen = {}4 if length == 0:5 return 16 if length in seen:7 return seen[length]8 total = count_bad(length - 1, False, seen)9 if not last_was_one:10 total += count_bad(length - 1, True, seen)11 seen[length] = total12 return total13 14def count_good(length, last_was_one=False, seen=None):15 if seen is None:16 seen = {}17 if length == 0:18 return 119 key = (length, last_was_one)20 if key in seen:21 return seen[key]22 total = count_good(length - 1, False, seen)23 if not last_was_one:24 total += count_good(length - 1, True, seen)25 seen[key] = total26 return total27 28print(count_bad(10), count_good(10))