Cutting the table down

Most tables are far larger than they need to be. Reducing them is mechanical, and it costs something specific.

Two rows to one row

If a cell reads only the row above and the cell to the left, one array works:

for r in range(rows):
    for c in range(1, cols):
        row[c] = row[c] + row[c-1]
        #        ^above    ^current, already updated this pass

Left to right is required, because row[c-1] must be the current row and row[c] must still be the previous one. Reverse the direction and both are wrong.

The knapsack direction

for w, v in items:
    for c in range(C, w - 1, -1):          # downward
        best[c] = max(best[c], v + best[c - w])

Downward means best[c - w] still holds the state before this item, so the item is used at most once. Upward means it may already include this item, so it is reused, and the code now solves the unbounded problem.

The direction is not a style choice. It selects which problem is being solved, and this is the single most common silent error in the subject.

To a few variables

When only the previous one or two cells are read, drop the array entirely:

a, b = 0, 1
for _ in range(n):
    a, b = b, a + b

O(n) to O(1).

What it costs

Reconstruction walks backwards through the table asking which neighbour each cell came from. Roll the table and those rows no longer exist.

So the decision is: do you need the value, or the thing that produced it?

When not to bother

If the table fits comfortably, keep it. It is easier to debug, because you can print it and inspect it, and it preserves reconstruction. Optimise when memory is the actual constraint, not reflexively.

Where both are needed, Hirschberg's divide and conquer recovers the alignment in linear space at about twice the time, and knowing it exists is usually enough.