Module 23 · Dynamic Programming I: One-Dimensional State

221. Fibonacci with Rolling State

Foundation · Download this solution · All solutions and shared helpers

Problem

Return Fibonacci number F(n) for integer n>=0, with F(0)=0, F(1)=1 and F(n)=F(n-1)+F(n-2). Use a constant number of integer variables rather than a table. Python integers preserve the exact result.

Examples

Example 1

fibonacci(7)
=> 13

Seven pair advances leave F(7) in previous.

Example 2

fibonacci(0)
=> 0

No update changes the defining base value.

Example 3

fibonacci(1)
=> 1

One update reaches the second base value.

Reveal the worked solution and reasoning

Why this mechanism works

The recurrence needs only two consecutive answers. Define the rolling state before coding its assignment: at iteration i, previous is F(i) and current is F(i+1). Advancing both simultaneously retains the old pair long enough to compute the next one.

State and boundaries

Before iteration i, (previous,current)=(F(i),F(i+1)). The loop advances this pair exactly n times.

Protocol

Initialize (0,1).
Repeat n times.
Assign previous=current and current=old_previous+old_current simultaneously.
Return previous.

Visualization

i=0: (0,1)
i=1: (1,1)
i=2: (1,2)
i=3: (2,3) -> previous is F(3)

Python implementation

def fibonacci(n):
    previous, current = 0, 1
    for _ in range(n):
        previous, current = current, previous + current
    return previous

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

fibonacci(7)

L2 fibonacci: previous, current = 0, 1
n=7; previous=0; current=1

L3 fibonacci: for _ in range(n):
n=7; previous=0; current=1; _=0

L4 fibonacci: previous, current = current, previous + current
n=7; previous=1; current=1; _=0

L3 fibonacci: for _ in range(n):
n=7; previous=1; current=1; _=1

L4 fibonacci: previous, current = current, previous + current
n=7; previous=1; current=2; _=1

L3 fibonacci: for _ in range(n):
n=7; previous=1; current=2; _=2

L4 fibonacci: previous, current = current, previous + current
n=7; previous=2; current=3; _=2

L3 fibonacci: for _ in range(n):
n=7; previous=2; current=3; _=3

... 3 intermediate state changes omitted ...

L3 fibonacci: for _ in range(n):
n=7; previous=5; current=8; _=5

L4 fibonacci: previous, current = current, previous + current
n=7; previous=8; current=13; _=5

L3 fibonacci: for _ in range(n):
n=7; previous=8; current=13; _=6

L4 fibonacci: previous, current = current, previous + current
n=7; previous=13; current=21; _=6

Result: 13. Seven pair advances leave F(7) in previous.

fibonacci(0)

L2 fibonacci: previous, current = 0, 1
n=0; previous=0; current=1

Result: 0. No update changes the defining base value.

Why the solution is correct

The initial pair is the two defining base values. The Fibonacci recurrence transforms a correct consecutive pair into the next consecutive pair, preserving the invariant. After n advances previous is exactly F(n). The fixed iteration count establishes termination.

Time and space

O(n) additions and O(1) integer variables. Exact Fibonacci values have O(n) bits, so bit storage is O(n) and total elementary bit work for these additions is O(n^2), not literal constant-byte space.

Common mistakes

Sequentially overwriting previous before forming the sum adds the new current twice. Returning current gives F(n+1) under this invariant.

Reasoning card

State: Before iteration i, (previous,current)=(F(i),F(i+1)). The loop advances this pair exactly n times.

Invariant: previous and current are consecutive Fibonacci values.

Decision to rehearse: Update consecutive states simultaneously.

Finish: Return previous

Transfer exercise

Derive fast doubling identities to reduce the number of arithmetic operations to O(log n).