Keeping Only the Entries the Recurrence Reads

If each entry needs only the two before it, two variables replace the table.

When each entry of a table depends only on a fixed number of entries just before it, the rest of the table is never read again, and a few variables rolled forward can replace it. This card shows the stall problem going from a table of n entries to two variables, and what the smaller version gives up.

The no-neighbours recurrence, dp[i] = max(dp[i − 1], dp[i − 2] + takings[i]), reads two entries: the one just before and the one before that. Once dp[i] is computed, dp[i − 2] is never needed again. The listing below keeps the whole table anyway, and runs on the four stalls 3, 2, 7 and 10 and on seven stalls 6, 7, 1, 30, 8, 2 and 4.

rolling_table.pypy

def best_total(takings: list[int]) -> int:
    table = [0] * (len(takings) + 2)
    for i, value in enumerate(takings):
        table[i + 2] = max(table[i + 1], table[i] + value)
    return table[-1]


print(best_total([3, 2, 7, 10]), best_total([6, 7, 1, 30, 8, 2, 4]))

OutputRan with python:3.14.8-slim-trixie (Python 3.14.8)

13 41

The version below keeps only the two entries the recurrence reads, named for what they hold, and moves them along one stall at a time. The tuple assignment in line 4 computes the new best from the old pair before either is overwritten.

rolling_vars.pypy

def best_total(takings: list[int]) -> int:
    before_last, last = 0, 0
    for value in takings:
        before_last, last = last, max(last, before_last + value)
    return last


print(best_total([3, 2, 7, 10]), best_total([6, 7, 1, 30, 8, 2, 4]))

OutputRan with python:3.14.8-slim-trixie (Python 3.14.8)

13 41

Both printed 13 and 41. The time is O(n) either way, but the space falls from O(n) to O(1): two numbers instead of one per stall. Fibonacci rolls the same way, and the general rule is that a recurrence reading the k entries before it needs k variables, or a small array used as a ring. For a table with two indices, such as the knapsack in Knapsack and Grid Dynamic Programming, a later topic, the same idea keeps one or two rows instead of the whole grid.

The table recorded the best total for every prefix, and walking back through it recovers which stalls were chosen: stall i was taken wherever dp[i] differs from dp[i − 1]. The two variables keep only the final total, so the choices are gone. Roll the state when the question asks for a number; keep the table when it asks which items make it.

Rolling suits tabulation, which visits states in a fixed order and can discard each once the loop has moved past it. A memo cannot discard anything, because a recursive call may ask for any stored state again.

← → move through sections and cards