Micro-Drill #154 — Space optimization: rolling array

SPACE OPTIMIZATION PATTERNS
────────────────────────────
# 2D → 1D (when row i only depends on row i-1):
# BEFORE: O(n*m) space
dp = [[0]*(m+1) for _ in range(n+1)]
for i in range(1, n+1):
    for j in range(1, m+1):
        dp[i][j] = dp[i-1][j-1] + 1  # example

# AFTER: O(m) space — two rows
prev, curr = [0]*(m+1), [0]*(m+1)
for i in range(1, n+1):
    for j in range(1, m+1):
        curr[j] = prev[j-1] + 1
    prev, curr = curr, [0]*(m+1)

# 1D → O(1) (when dp[i] only needs dp[i-1], dp[i-2]):
# BEFORE:
dp = [0] * n
# AFTER:
a, b = base0, base1
for i in range(2, n):
    a, b = b, f(a, b)

KEY: iterate inner loop BACKWARDS for 0/1 knapsack
     to avoid using updated values.