Fibonacci tabulation

Compute Fibonacci with a table.

Fibonacci tabulation

Fibonacci tabulation: build an array, dp[0]=0, dp[1]=1, then dp[i] = dp[i-1] + dp[i-2].

This computes Fibonacci without recursion or cache; very efficient.

Tabulation gives Θ(n) time and Θ(n) memory; it can be reduced to Θ(1) memory with a single variable.

Memory optimization

Keeping only two previous values removes the need for the whole table; memory becomes Θ(1).

But the table method makes tracing easier in general DP problems; it is preferred in teaching.

The two-variable solution avoids cache complexity; speed is preserved.

Exercise Fibonacci optimization

Write fib_opt(n). Compute Fibonacci with only two variables. Print 55 with print(fib_opt(10)).

Show example solution

def fib_opt(n):
    # Fibonacci optimization
    if n <= 1:
        return n
    prev2 = 0
    prev1 = 1
    for i in range(2, n + 1):
        curr = prev1 + prev2
        prev2 = prev1
        prev1 = curr
    return prev1
print(fib_opt(10))

Test yourself

Fibonacci tabulation: match the terms

dp

Table
i-1

Previous
i-2

Two back
O(n)

Linear
What is Fibonacci tabulation's memory complexity?
- Θ(1)
- Θ(n)
- Θ(log n)
- Θ(n^2)
Show answer

Θ(n) — Θ(n).

Loop body

dp[i] = dp[i - 1] + dp[i - ____]

Show answer

dp[i] = dp[i - 1] + dp[i - 2]

Next lesson: Summary - Tabulation

We Are Enhancing Your Experience

Cookie Preferences

Strictly Necessary Cookies

Analytical Cookies