Pick-or-skip DP with adjacency rules

Pick-or-skip DP chooses items from a line when taking an item rules out its neighbours: stalls along a lane, houses on a street, shifts on consecutive days. Each item is either taken or skipped, and a choice reaches only one place forward, so a table with one entry per item and two choices per entry finds the largest total in linear time. A ring adds one rule, that the first and the last items are neighbours too. This lesson poses both shapes as original problems, the row and the ring, and shows why trying every set of items cannot work.

Two problems: stalls in a row, lamps in a ring

Problem A, stalls in a row. A market lane has n stalls in a row, and stall i gives a discount of discounts[i]. Two neighbouring stalls share one counter that serves a shopper only once, so you never visit two stalls side by side. Return the largest total discount. Limits: 0 ≤ n ≤ 100,000 and 0 ≤ discounts[i] ≤ 10,000.

• [6, 2, 3, 9, 4] gives 15, from the stalls worth 6 and 9.
• [5, 9, 6] gives 11: the 9 is the largest, but taking it rules out both 5 and 6.
• [8, 1, 1, 8] gives 16, from the two ends.

Problem B, lamps in a ring. Lamp posts stand around a lake, and lamp i lights values[i] metres of the path. Neighbouring lamps share a fuse that cannot carry both, and the last lamp is the neighbour of the first. Same limits.

• [4, 1, 2, 7, 5, 3, 1] gives 14, from the lamps worth 4, 7 and 3.
• [9, 2, 9] gives 9: in a row the two 9s would give 18, but in the ring they are neighbours.

The brute force, and why it fails

Try every set of stalls, drop the sets with two neighbours, and keep the best total:

import math
from itertools import product


def best_visit_brute(discounts):
    """Tries every set of stalls, keeps those with no two neighbours, and returns the best total and how many sets it tried."""
    best, best_stalls, tried = 0, [], 0
    for visit in product((False, True), repeat=len(discounts)):
        tried += 1
        if any(visit[i] and visit[i + 1] for i in range(len(visit) - 1)):
            continue  # two neighbouring stalls
        total = sum(d for d, v in zip(discounts, visit) if v)
        if total > best:
            best, best_stalls = total, [i for i, v in enumerate(visit) if v]
    return best, best_stalls, tried


for discounts in ([6, 2, 3, 9, 4], [5, 9, 6], [8, 1, 1, 8], [7]):
    best, stalls, tried = best_visit_brute(discounts)
    print(f"{discounts}: {best}, from stalls {stalls} ({tried} sets tried)")


def allowed_sets(n):
    """How many sets of stalls have no two neighbours, counted without listing them."""
    with_last, without_last = 0, 1  # for a row of 0 stalls: only the empty set
    for _ in range(n):
        with_last, without_last = without_last, with_last + without_last
    return with_last + without_last


for n in (10, 20, 40, 100_000):
    count = allowed_sets(n)
    if n < 1000:
        print(f"{n:,} stalls: {count:,} allowed sets")
    else:
        print(f"{n:,} stalls: a number of allowed sets with {int(math.log10(count)) + 1:,} digits")

[6, 2, 3, 9, 4]: 15, from stalls [0, 3] (32 sets tried)
[5, 9, 6]: 11, from stalls [0, 2] (8 sets tried)
[8, 1, 1, 8]: 16, from stalls [0, 3] (16 sets tried)
[7]: 7, from stalls [0] (2 sets tried)
10 stalls: 144 allowed sets
20 stalls: 17,711 allowed sets
40 stalls: 267,914,296 allowed sets
100,000 stalls: a number of allowed sets with 20,899 digits

The answers are right, but 5 stalls already need 32 sets, and the allowed sets alone grow by a factor of about 1.6 per stall: 144 for 10 stalls, 267,914,296 for 40, and for 100,000 stalls a count with 20,899 digits. The counts are Fibonacci numbers, so no listing of them can finish at the stated size.

What to notice

• Every item has two choices, take or skip, and taking it rules out only the items just before and just after it.
• The largest item is not always taken, because it can block two neighbours worth more, as in [5, 9, 6].
• The ring differs from the row in one pair, the first and the last item, so fixing what happens at one end turns it back into a row.

The choice at each stall, and why it is enough Pro: opens with a Pro, Premium or Ultimate pass