Same dependencies, two ways to evaluate them

Picture

Memoization starts with the requested answer and recursively asks for dependencies, remembering completed results. Tabulation starts with known small answers and evaluates larger ones in a valid order. These are evaluation strategies for a recurrence, not different meanings of the underlying problem.

Predict

For ways(n) = ways(n-1) + ways(n-2), can you fill a table from large indices down to small ones if the entries initially contain zero?

Reveal the reasoning

Not with that recurrence and those initial values. Its dependencies live at smaller indices and must be ready first. Another recurrence using suffixes could have another valid order.

Go deeper: a table is an evaluation schedule

def count_climbs(n):
    table = [0] * (n + 1)
    table[0] = 1
    for height in range(1, n + 1):
        table[height] = table[height - 1]
        if height >= 2:
            table[height] += table[height - 2]
    return table[n]

assert [count_climbs(n) for n in range(6)] == [1, 1, 2, 3, 5, 8]

After each iteration, all entries up to height are correct. The table is a topological evaluation of dependencies from smaller heights to larger heights. Both this and the preceding memoized version use O(n) arithmetic operations and O(n) storage. Tabulation removes recursive calls; it is not automatically asymptotically faster.

Memoization can avoid unreachable states when the theoretical state space is large but sparse. Tabulation offers direct control over order and memory reuse and avoids Python call-depth limits. Choose after identifying state and transitions.

Use this derivation worksheet: meaning of one state; legal first or last choices; base and impossible cases; proof of smaller dependencies; total state count; work per state; location of the requested answer.

Do not decorate arbitrary cyclic recursion with @cache and expect it to terminate. A result is recorded after its call returns; an active call depending on itself still has no completed result to reuse. Some problems need a different state or another algorithm entirely.

Analogy limit: a spreadsheet appearance does not make an algorithm DP. The dependency relation and reused subproblem answers are what matter.

Change one rule

You only need the final climb count. Must you retain every earlier count?

Check the variation

No. Only the two preceding counts feed the next one, so two rolling values suffice. This changes storage, not the logical meaning of the state.

Connect

1D DP derives a different recurrence. Grid DP uses row/column dependencies. Compression asks when earlier storage is safe to overwrite.