Take it or skip it

The first real choice. Two options per element, and the constraint decides what taking costs you.

Key idea

The shape

A great many problems reduce to walking a list and deciding, at each element, whether to take it. The constraint is what makes it interesting: taking something usually forbids taking something else.

The recursion is two calls. Take this element, add its value, and continue from wherever the constraint allows. Or skip it and continue from the next one. Return the better of the two.

Below is that comparison at a single position, with the answers from further right assumed already known. Taking an item here forbids the next gap items, so the take branch jumps further than the skip branch.

1values = [5, 1, 1, 5]2gap = 13 4# Best obtainable starting at each index, for the part already worked out.5best_from = {2: 5, 3: 5, 4: 0}6 7index = 18take = values[index] + best_from[index + gap + 1]9skip = best_from[index + 1]10print("take:", take, " skip:", skip, " -> best from index 1 is", max(take, skip))

Taking the 1 at index 1 rules out index 2, so the take branch continues from index 3.

Predict the output· 5 min

Predict the output: what the constraint actually forbids

Every selection of non-adjacent positions from four values is listed, with its total. Type the two lines it prints.

Python

1values = [5, 1, 1, 5]2 3def selections(n):4    if n == 0:5        yield []6        return7    for rest in selections(n - 1):8        yield rest9        if not rest or rest[0] > n:              # positions are added descending10            yield [n - 1] + rest if False else rest11 12allowed = []13for mask in range(1 << len(values)):14    picked = [i for i in range(len(values)) if mask >> i & 1]15    if all(b - a > 1 for a, b in zip(picked, picked[1:])):16        allowed.append(picked)17 18print(len(allowed), "legal selections")19print("best total:", max(sum(values[i] for i in picked) for picked in allowed))

Printed output

Problem· 22 min

House Robber

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.

1values = [5, 1, 1, 5]2gap = 13 4# Best obtainable starting at each index, for the part already worked out.5best_from = {2: 5, 3: 5, 4: 0}6 7index = 18take = values[index] + best_from[index + gap + 1]9skip = best_from[index + 1]10print("take:", take, " skip:", skip, " -> best from index 1 is", max(take, skip))

1values = [5, 1, 1, 5]2 3def selections(n):4 if n == 0:5 yield []6 return7 for rest in selections(n - 1):8 yield rest9 if not rest or rest[0] > n: # positions are added descending10 yield [n - 1] + rest if False else rest11 12allowed = []13for mask in range(1 << len(values)):14 picked = [i for i in range(len(values)) if mask >> i & 1]15 if all(b - a > 1 for a, b in zip(picked, picked[1:])):16 allowed.append(picked)17 18print(len(allowed), "legal selections")19print("best total:", max(sum(values[i] for i in picked) for picked in allowed))