Skip to main content

Fibonacci and the Rolling-Array Space Reduction

What This Concept Is​

Fibonacci is the smallest non-trivial DP. It is worth studying not for its own sake -- closed forms exist via Binet's formula -- but because it isolates one structural observation cleanly:

When the recurrence for dp[i] only depends on a fixed constant number of previous entries, you do not need to store the whole table. You only need those previous entries.

This is the rolling-array (or "rolling-window") space reduction. The technique generalizes: whenever $dp[i]$ depends only on $dp[i-1]$ and $dp[i-2]$, you can keep $O(1)$ state; whenever $dp[i][j]$ depends only on $dp[i-1][*]$, you can keep $O(j)$ state instead of $O(ij)$. The idea is locality of dependence: identify the recurrence's footprint, keep only that footprint live.

The technique applies equally to memoization and tabulation, but it is most natural in tabulation because tabulation already controls the fill order. In memoization you cannot roll without effectively reimplementing the fill order yourself.

More formally: a recurrence $dp[i] = f(dp[i-1], dp[i-2], \ldots, dp[i-k])$ reads a window of $k$ previous entries. You keep a ring buffer of length $k$ instead of a full array of length $n$. Space: $O(k)$ instead of $O(n)$. The same idea extended to 2D: if $dp[i][j]$ reads only the previous row, keep two rows. If it reads two previous rows, keep three. And so on.

Why It Matters Here​

Naive Fibonacci is $O(2^n)$. Memoization brings it to $O(n)$ time and $O(n)$ space. A rolling-array bottom-up version is $O(n)$ time and $O(1)$ space. These are three different answers to the same problem, and the same rung-by-rung improvement applies to most sequence DPs.

For $n = 10^9$, the difference between $O(n)$ space and $O(1)$ space is the difference between running and out-of-memory. For embedded or memory-budgeted systems (e.g., streaming DP on edge devices), rolling arrays are not a luxury -- they are the only way the DP fits.

The trick also generalizes across the module: knapsack's single-array $O(W)$ form, edit distance's two-row $O(n)$ form, and LIS's patience-sort state all share the same "only keep what the recurrence reads" reasoning.

Concrete Examples​

Full table Fibonacci:

def fib(n):
    if n < 2: return n
    dp = [0] * (n + 1)
    dp[1] = 1
    for i in range(2, n + 1):
        dp[i] = dp[i-1] + dp[i-2]
    return dp[n]

Space: $O(n)$. Recurrence: $F(n) = F(n-1) + F(n-2)$.

Rolling-window Fibonacci:

def fib(n):
    if n < 2: return n
    a, b = 0, 1
    for _ in range(2, n + 1):
        a, b = b, a + b
    return b

Space: $O(1)$. Time is the same. You keep exactly the two entries the recurrence reads.

Trace for $n = 6$:

stepabcomment
init01$F_0, F_1$
111$F_1, F_2$
212$F_2, F_3$
323$F_3, F_4$
435$F_4, F_5$
558$F_5, F_6$

Return b = 8. $F_6 = 8$. ✓

Knapsack rolling. $dp[i][w]$ depends only on $dp[i-1][*]$, so you can process items iteratively over a single array $dp[0..W]$, updating $w$ in descending order for 0/1 (to avoid reusing an item) or ascending order for unbounded (to deliberately reuse an item). Space: $O(W)$ instead of $O(nW)$.

Edit distance two-row rolling. $dp[i][j]$ depends only on $dp[i-1][j-1]$, $dp[i-1][j]$, $dp[i][j-1]$. Keep prev and cur rows, $O(n)$ space.

0/1 knapsack rolling trace for items $(2,3),(3,4)$, $W=5$. Full table would be $3 \times 6$. Single-array iteration on dp[0..5], initialised to zeros:

  • process $(2,3)$, $c$ from $5$ down to $2$: dp = [0,0,3,3,3,3].
  • process $(3,4)$, $c$ from $5$ down to $3$: at $c=5$, $dp[5]=\max(3, dp[2]+4)=7$; at $c=4$, $dp[4]=\max(3,dp[1]+4)=4$; at $c=3$, $dp[3]=\max(3,dp[0]+4)=4$. Final: dp = [0,0,3,4,4,7]. ✓

The descending loop is the whole point: $dp[c-w]$ still holds "before this item," preventing double-counting.

Common Confusion / Misconceptions​

"Rolling is free." It is not -- it deletes information you may later want to recover. If you need reconstruction, you need the choice at each step, which usually forces you back to the full table (or at least a compact choice log). Rolling is a space optimization for "value only" computations.

"Rolling the wrong dimension." In 2D DP, you must roll the dimension whose dependence "steps" by a fixed amount. If $dp[i][j]$ depends on $dp[i][j-1]$, you roll over $i$ (keeping a whole row), not $j$. Reversing this produces subtle off-by-one bugs.

"Window size equals recurrence arity." Not always. For $dp[i] = dp[i-1] + dp[i-3]$, you need a window of size 3 ($dp[i-1]$, $dp[i-2]$, $dp[i-3]$ must all be live when computing $dp[i]$, even though $dp[i-2]$ is not read -- it will be read on the next step). Trace the dependency graph; do not shrink the window below what the next iteration needs.

"Rolling works in memoization." Usually not in a clean way. Memoization's cache is by state key, not by fill order. To "roll" a memoized DP you would have to manually garbage-collect the cache by fill layer, which is brittle. Tabulation is the natural home of rolling arrays.

How To Use It​

  1. Write the full-table recurrence first and verify correctness on a small example by hand.
  2. Identify which previous row(s) or entry(ies) $dp[i]$ actually reads from.
  3. Identify the fill order -- usually it is given by your tabulation loop structure.
  4. Keep only the rows/entries that at least one future step will still read. Usually $O(1)$ or $O(\text{row})$ entries.
  5. If you also need the optimal object, either keep the full table or log the choice separately.
  6. Double-check the update order: for 0/1 knapsack's single-array form, $w$ goes descending to prevent reusing an item in the current iteration; reversing the order silently changes semantics.
  7. Verify the rolled version against the full-table version on ≥ 10 random small inputs.

Transfer / Where This Shows Up Later​

  • S3 Software Design. Rolling-array state is a pattern for bounded memory stateful computations -- the same discipline as a Ring Buffer in producer/consumer or a Sliding-Window in rate limiters.
  • S5 Networking. TCP keeps a bounded window of in-flight segments; the state is exactly "what depends on the recent past" -- same locality argument.
  • S6 Databases. Streaming aggregations over windows (tumbling, hopping, sliding) are rolling-state DPs: keep only the window, emit, advance.
  • S7 Architecture. "Only keep hot state in memory; the rest is cold storage" is an architectural rolling-array argument.
  • Phase 7 AI. In reinforcement learning, n-step bootstrapping and eligibility traces are rolling-state techniques for value estimation -- same structural idea, different domain.

Check Yourself​

  1. Why does rolling not generally work if you need to reconstruct the optimal object?
  2. For a recurrence $dp[i][j] = f(dp[i-1][j], dp[i-1][j-1])$, how many rows must you keep?
  3. If $dp[i] = dp[i-1] + dp[i-3]$, how many values must you keep in the rolling window, and why?
  4. In 0/1 knapsack's single-array form, why does the loop over $w$ go from $W$ down to $w_i$, not ascending?
  5. Name one DP where rolling is impossible without extra state, and explain why.
  6. How does Hirschberg's algorithm combine rolling with divide-and-conquer to reconstruct without a full table?

Mini Drill or Application​

Implement the following two ways each -- full table, then rolling:

  1. climb_stairs(n) with 1 or 2 steps.
  2. fib_mod_m(n, m) (Fibonacci modulo $m$, useful for overflow control).
  3. min_cost_stairs(cost[]) where you pay cost[i] to stand on step $i$ and can start on step 0 or 1.
  4. Unbounded coin change: minimum coins for amount $A$, with denominations given. Use the ascending-$c$ single-array form.
  5. 0/1 knapsack: maximum value, single-array descending-$w$ form.

For each, print peak memory usage and confirm that the rolling version matches the full-table result on a small input. Then try $n = 10^7$ on both versions and observe behavior -- the full table will OOM or swap; the rolled version will finish.

Read This Only If Stuck​