Card 03/ 10
Swapping the Two Choices in the Recurrence
Adding the value to the wrong term lets two neighbours both be taken, and the answer grows.
A recurrence with two choices can be written with its terms swapped, adding the new value to the entry next door instead of the one two back, and the result runs, returns a number, and is wrong. This card shows the swap on the no-neighbours problem from Define a State and a Recurrence, Then Check Them by Hand, and the hand check that catches it.
The symptom is an answer that is too large. The trigger is a version that rolls two variables forward, where prev holds the best from two stalls back and curr the best from one back. The two names look alike, and the right line, max(curr, prev + v), is easy to type as max(prev, curr + v). The listing below has that swap, and prints the best total after each of four stalls holding 5, 1, 1 and 5.
def best_total(values: list[int]) -> list[int]:
dp, prev, curr = [], 0, 0
for v in values:
prev, curr = curr, max(prev, curr + v)
dp.append(curr)
return dp
print(best_total([5, 1, 1, 5]))[5, 6, 7, 12]The final 12 is the sum of all four stalls, which no valid choice can reach. The mechanism is in line 4: curr + v adds this stall to the best that may already include its neighbour, so each step takes the stall whatever happened next door, and the total grows with every value. The listing below has the two terms the right way round, and adds the stall to the best from two back.
def best_total(values: list[int]) -> list[int]:
dp, prev, curr = [], 0, 0
for v in values:
prev, curr = curr, max(curr, prev + v)
dp.append(curr)
return dp
print(best_total([5, 1, 1, 5]))[5, 5, 6, 10]Ten, from the first and last stalls. The cost of the swap is a wrong answer with no error. With every value positive, the swapped line always takes the stall, so it returns the sum of the whole list, a number that looks plausible for a long input, and a test that checks only that the code runs and returns a number passes.
The remedy is the hand check. Work out the answer for four values by eye, then run the recurrence on them before trusting it. On 5, 1, 1 and 5, the second entry is the giveaway: with two stalls the best is the larger of 5 and 1, and the swapped version printed 6, which takes both neighbours.
← → move through sections and cards