1-D dynamic programming: take or skip

One-dimensional dynamic programming (1-D DP) solves a problem over a sequence with one table entry per position: best[i] is the answer for the first i items, and each entry is worked out from a few entries just before it, so one pass over the sequence fills the table in O(n) time. The most common shape is take or skip. On a street where two neighbouring houses may not both be visited, house i is either skipped, which leaves best[i − 1], or taken, which adds its gift to best[i − 2], the best that stops short of its neighbour. So best[i] is the larger of best[i − 1] and best[i − 2] + gift(i). Because each entry looks back only two places, two variables can replace the table, and walking back through the table tells you which houses were chosen. This lesson traces the recurrence on a street of eight houses, runs it, cuts its memory to two numbers and rebuilds the choice.

A street of donations

A volunteer collects donations along a street of eight houses. The housing society asks that no two neighbouring houses are visited on the same day, and the gifts on offer are 40, 10, 60, 50, 20, 90, 30 and 70. Which houses should the volunteer visit to collect the most?

The obvious plans fall short. Every other house gives 40 + 60 + 20 + 30 = 150 from the odd houses, or 220 from the even ones. Trying every allowed set works for eight houses, which allow only 55 sets, but the count grows like the Fibonacci numbers, by about 1.6 for each extra house: a street of 100 houses allows about 9.3 × 10²⁰ of them.

Skip or take: the recurrence

Write the DP in its four parts. The state is best[i], the most that the first i houses can give. The transition looks at house i, the last of them, which is either skipped or taken:

The base cases are best[0] = 0 for an empty street and best[1] = gift(1), which the rule also gives if best[−1] is read as 0. The answer is best[n]. Filling i from 1 up to n keeps every entry after the two it reads.

The table, traced on the street

"""The most donations along a street when two neighbouring houses may not both be visited."""
import random
from itertools import product

donations = [40, 10, 60, 50, 20, 90, 30, 70]


def best_table(d):
    """best[i]: the most that the first i houses can give; best[0] = 0, a street with no houses."""
    best = [0] * (len(d) + 1)
    for i in range(1, len(d) + 1):
        skip = best[i - 1]
        take = (best[i - 2] if i >= 2 else 0) + d[i - 1]
        best[i] = max(skip, take)
    return best


def chosen_houses(d, best):
    """Walk back from the last house: an entry equal to the one before it means the house was skipped."""
    houses, i = [], len(d)
    while i >= 1:
        if best[i] == best[i - 1]:
            i -= 1
        else:
            houses.append(i)
            i -= 2
    return houses[::-1]


def best_two_numbers(d):
    before, last = 0, 0  # best[i - 2] and best[i - 1]
    for x in d:
        before, last = last, max(last, before + x)
    return last


def every_selection(d):
    best = 0
    for picks in product((0, 1), repeat=len(d)):
        if not any(picks[i] and picks[i + 1] for i in range(len(d) - 1)):
            best = max(best, sum(x for x, p in zip(d, picks) if p))
    return best


best = best_table(donations)
print(f"{'house':>5} {'gift':>5} {'skip':>5} {'take':>5} {'best':>5}")
for i in range(1, len(donations) + 1):
    take = (best[i - 2] if i >= 2 else 0) + donations[i - 1]
    print(f"{i:>5} {donations[i - 1]:>5} {best[i - 1]:>5} {take:>5} {best[i]:>5}")
houses = chosen_houses(donations, best)
print(f"houses visited: {houses}, total {sum(donations[h - 1] for h in houses)}")
print(f"two numbers instead of a table: {best_two_numbers(donations)}")
print(f"every allowed selection tried: {every_selection(donations)}")

rng = random.Random(5)
streets = [[rng.randint(0, 99) for _ in range(rng.randint(0, 12))] for _ in range(2_000)]
agree = all(best_table(s)[-1] == best_two_numbers(s) == every_selection(s) for s in streets)
print(f"2,000 random streets of 0 to 12 houses, table = two numbers = every selection: {agree}")

house  gift  skip  take  best
    1    40     0    40    40
    2    10    40    10    40
    3    60    40   100   100
    4    50   100    90   100
    5    20   100   120   120
    6    90   120   190   190
    7    30   190   150   190
    8    70   190   260   260
houses visited: [1, 3, 6, 8], total 260
two numbers instead of a table: 260
every allowed selection tried: 260
2,000 random streets of 0 to 12 houses, table = two numbers = every selection: True

Read a few rows. At house 3, taking it gives 60 + best[1] = 100, more than the 40 of skipping it. At house 4, taking gives only 50 + 40 = 90, so best[4] stays 100. House 6 is worth taking, 90 + 100 = 190, and house 8 lifts the total to 70 + 190 = 260.

The table stores totals, not houses, but the houses can be read back from it. Start at the last house. If best[i] equals best[i − 1], house i can be skipped without loss, so move to i − 1. Otherwise house i was taken: record it and jump to i − 2, past its neighbour. Here the walk takes house 8, jumps to 6 and takes it, skips 4, takes 3, jumps to 1 and takes it: houses 1, 3, 6 and 8 for 260. The run checks that answer against all 55 allowed sets, and the table against the same search on 2,000 random streets.

Two numbers instead of a table

Each entry reads only the two entries before it, so once best[i] is known, best[i − 2] is never read again. Keeping two variables, before and last, cuts the memory from O(n) to O(1) and still gives 260. The price is the walk back, which needs every entry: keep the table, or one bit per house that records the choice, when the houses matter, and the two numbers when only the total does.

The same shape in other problems

Many problems are this table with a different look-back:

• Digit decodings. Counting the ways to read a string of digits as letters adds the two entries before each position, but only when those digits form a letter.
• A circular street. When the first and last houses are neighbours too, the answer is the better of two straight streets.
• Weighted interval scheduling. For paid gigs with start and end times, taking a gig looks back to the last gig that ends before it starts.
• Rest days. If every working day needs k rest days after it, taking a day looks back k + 1 places, which the exercise asks you to write.

Exercise

def best_days(values, k):
    """The largest total of values[d] over working days d, with at least k rest days after each working day."""
    # This solves k = 1 only: taking day i adds to the best up to two days earlier.
    # Change how far back "take" looks so that it works for any k >= 0.
    before, last = 0, 0
    for v in values:
        before, last = last, max(last, before + v)
    return last

import random
from itertools import combinations

from rest_days import best_days


def slow_best(values, k):
    """Every set of days, kept when consecutive working days are at least k + 1 apart."""
    best = 0
    for r in range(len(values) + 1):
        for days in combinations(range(len(values)), r):
            if all(b - a > k for a, b in zip(days, days[1:])):
                best = max(best, sum(values[d] for d in days))
    return best


def test_one_rest_day():
    """k = 1 is the street of houses: no two neighbouring days"""
    assert best_days([40, 10, 60, 50, 20, 90, 30, 70], 1) == 260


def test_no_rest_needed():
    """k = 0: every day can be a working day"""
    assert best_days([3, 1, 4, 1, 5], 0) == 14


def test_two_rest_days():
    """k = 2: days 0, 3 and 6; and two of the three 9s, since 9s two days apart are too close"""
    assert best_days([5, 1, 1, 5, 1, 1, 5], 2) == 15
    assert best_days([9, 1, 9, 1, 9], 2) == 18


def test_rest_longer_than_the_season():
    """a k longer than the season leaves room for one working day: the best single day"""
    assert best_days([4, 8, 2, 6], 10) == 8


def test_empty_season():
    """no days, no earnings"""
    assert best_days([], 3) == 0


def test_against_every_set_of_days():
    """300 random seasons of up to 10 days and k from 0 to 4"""
    rng = random.Random(12)
    for _ in range(300):
        values = [rng.randint(0, 20) for _ in range(rng.randint(0, 10))]
        k = rng.randint(0, 4)
        assert best_days(values, k) == slow_best(values, k), (values, k)

Why take-or-skip is right, and four bugs that break it Pro: opens with a Pro, Premium or Ultimate pass

Digit decodings, a circular street and paid gigs, solved and checked Pro: opens with a Pro, Premium or Ultimate pass

The street in five languages, and the 32-bit total that breaks it Pro: opens with a Pro, Premium or Ultimate pass

Interview questions

Key takeaways

• 1-D DP keeps one entry per position, best[i] for the first i items, and fills it in one pass.
• Take or skip: best[i] is the larger of best[i − 1] and best[i − 2] + gift(i), with best[0] = 0.
• On the lesson’s street the table finds 260 from houses 1, 3, 6 and 8, where every other house gives at most 220.
• Two variables are enough for the total; the walk back to the chosen items needs the table or a record of choices.