Dynamic Programming Tabulation: Build the Table Bottom-Up

Memoization is lovely until the input is large enough that the recursion runs out of stack. A river crossing with 50,000 stepping stones, each charging a toll, will crash a recursive solution with a RecursionError long before it runs out of time. The same logic written as a loop has no such limit. That is tabulation: instead of asking for answers on demand, you compute every smaller answer first, in an order that makes each one available when needed.

A problem to build the table for

A river has stones in a row. Landing on stone i costs tolls[i]. You start on the near bank, can jump 1, 2 or 3 stones at a time, and want to reach the far bank paying as little as possible. The far bank counts as reachable from any of the last three stones.

Define the state first. Let best[i] be the cheapest total toll to be standing on stone i. To stand on stone i, you must have come from stone i-1, i-2 or i-3 (or from the near bank, which costs nothing), so best[i] = tolls[i] + min(best[i-1], best[i-2], best[i-3]). Each cell depends only on cells to its left, which dictates the fill order: left to right.

def cheapest_crossing(tolls):
    """tolls[i] = fee to land on stone i. Start on the bank before stone 0,
    finish on the bank after the last stone. Each jump covers 1, 2 or 3 stones."""
    n = len(tolls)
    INF = float("inf")
    # best[i] = cheapest total fee to be standing on stone i (i = 0..n-1)
    best = [INF] * n
    came_from = [None] * n
    for i in range(n):
        for jump in (1, 2, 3):
            prev = i - jump
            if prev < -1:
                continue
            base = 0 if prev == -1 else best[prev]
            if base + tolls[i] < best[i]:
                best[i] = base + tolls[i]
                came_from[i] = prev
    # the far bank can be reached from any of the last three stones
    finish = min(range(max(0, n - 3), n), key=lambda i: best[i])
    path = []
    i = finish
    while i != -1:
        path.append(i)
        i = came_from[i]
    return best[finish], path[::-1], best

tolls = [4, 2, 9, 1, 7, 3, 8, 2]
cost, path, table = cheapest_crossing(tolls)
print("tolls:", tolls)
print("table:", table)
print("cost :", cost)
print("path :", path)

tolls: [4, 2, 9, 1, 7, 3, 8, 2]
table: [4, 2, 9, 3, 9, 6, 11, 8]
cost : 6
path : [1, 3, 5]

Read the table as a story. Stone 1 costs 2 because you can jump straight onto it from the near bank (a two-stone jump) and skip stone 0 entirely. Stone 3 costs 3: land on stone 1 for 2, then pay 1. Stone 5 costs 6 and is one jump from the far bank, so the cheapest crossing is stones 1, 3, 5 for a toll of 6. The came_from array is the breadcrumb trail that lets us rebuild that route.

Notice what the loop does not do: it never calls itself and never asks "have I seen this before?". Because the fill order is left to right and every cell only reads cells to its left, the answer to any sub-question is guaranteed to exist by the time it is needed. The cost is easy to count as well: eight stones, three jumps each, so 24 tiny steps. For 50,000 stones it is 150,000 steps and no deep stack, which is exactly why production code and long inputs tend to prefer this form.

Why the base case is the trickiest line

The table starts as INF, meaning "not reachable yet", and the near bank is represented by index -1 with a cost of 0. It is tempting to initialise the table to zeros because zero looks harmless. It is not: zero means "free to reach", which is a claim. Here is what that mistake does to the same input.

tolls = [4, 2, 9, 1, 7, 3, 8, 2]
best = [0] * len(tolls)          # 0 looks harmless but lies about "unreached"
for i in range(len(tolls)):
    best[i] = tolls[i] + min(best[max(i-1,0)], best[max(i-2,0)], best[max(i-3,0)])
print(best)

[4, 6, 13, 5, 12, 8, 13, 10]

Compare with the correct table: stone 1 is now 6 instead of 2, because the buggy code forced the jump to come from stone 0. The loop also clamps indices with max(i-1, 0), so cells reach back to stone 0 as a fake predecessor. Nothing crashes; every number is just quietly wrong, which is the worst kind of bug. Initialise to the identity of your operation: infinity for a minimum, negative infinity for a maximum, 0 for a sum of counts.

Top-down and bottom-up must agree

A good habit is to write the memoised version too and compare the two on the same inputs. The recursive one is almost a direct transcription of the recurrence.

from functools import lru_cache

def cheapest_top_down(tolls):
    n = len(tolls)

    @lru_cache(maxsize=None)
    def best(i):
        if i < 0:
            return 0 if i == -1 else float("inf")
        return tolls[i] + min(best(i - 1), best(i - 2), best(i - 3))

    return min(best(i) for i in range(max(0, n - 3), n))

print(cheapest_top_down([4, 2, 9, 1, 7, 3, 8, 2]))

6

Common mistakes and the symptoms they cause

• Wrong fill order. If a cell reads a neighbour that has not been computed, you read the initial value (INF or 0) and get a silently wrong answer. Check that every dependency of cell i has a smaller index than i.
• Off-by-one on table size. Tables over amounts or lengths need n + 1 entries so that index 0 can mean "nothing". Forgetting it raises IndexError: list index out of range at the last cell.
• Adding to INF in integer code. float("inf") + 1 is fine in Python but overflows or wraps in languages with fixed-width integers. Use a large sentinel and guard before adding.
• Returning the number but not the path. Interviewers often ask "which stones?". Store the decision (came_from) as you fill, rather than reverse-engineering it afterwards.

How this shows up in real projects and interviews

Cheapest-route and minimum-cost problems over a line or grid are staples of coding rounds, and they are also real: cost-aware routing, pricing tiers, and resource scheduling all reduce to "best value of a state computed from earlier states". In an interview, say the state and recurrence aloud before writing a single loop, then state the fill order and base cases. If you get the recurrence right, the code is a transcription; if the recurrence is wrong, no amount of loop tuning will save it.