Turning the recursion into loops

A memoised recursion and a filled table compute the same numbers. The conversion is mechanical once you know what to look at.

The four steps

1. The memo key becomes the table index. solve(i, c) becomes table[i][c].

2. The base cases are written first, into the cells the recursion returned early for.

3. The loop order is the reverse of the recursion's direction. If solve(i) calls solve(i+1), the loop must run from high to low, so that i+1 is filled before i.

4. The recursive calls become table reads.

Worked

# top down
def solve(i, c):
    if i == n: return 0
    best = solve(i + 1, c)
    if w[i] <= c:
        best = max(best, v[i] + solve(i + 1, c - w[i]))
    return best

# bottom up
table = [[0] * (C + 1) for _ in range(n + 1)]     # step 2: row n is all zero
for i in range(n - 1, -1, -1):                     # step 3: downward
    for c in range(C + 1):
        table[i][c] = table[i + 1][c]              # step 4
        if w[i] <= c:
            table[i][c] = max(table[i][c], v[i] + table[i + 1][c - w[i]])
answer = table[0][C]

The body is the same expression with calls replaced by lookups.

Getting the direction right

This is the step that goes wrong. The rule is that a cell must be filled after everything it reads.

That last row is the interval case, and it is why the plain nested loop over i and j silently reads unfilled cells.

What is gained and lost

Verify the conversion

Keep both and compare them on random small inputs. They must agree on every one. It takes five minutes and catches a wrong loop direction immediately, which is otherwise a table of plausible numbers and a wrong final answer.