CodeBlanks Logo Icon CodeBlanks
Login Register

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.

Practice Fibonacci optimization

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

Starter code

solution.py
def fib_opt(n):
    # Fibonacci optimization

Sample solution

solution.py
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))

Expected output

55

Questions and answers

Review the lesson questions together with their answers. To test yourself, solve the lesson interactively.

1 Fibonacci tabulation: match the terms

Term Meaning
dp Table
i-1 Previous
i-2 Two back
O(n) Linear

2 What is Fibonacci tabulation's memory complexity?

  • Θ(1)
  • Θ(n) Correct answer
  • Θ(log n)
  • Θ(n^2)

Explanation: Θ(n).

3 Loop body

Question 
dp[i] = dp[i - 1] + dp[i - ____]
Answer 
dp[i] = dp[i - 1] + dp[i - 2]

Explanation: 2 is right.

All lessons in Advanced

1 DP - Memoization

  1. What is memoization?
  2. Fibonacci memoization
  3. Dict-based cache
  4. Summary - Memoization

2 DP - Tabulation

  1. What is tabulation?
  2. Building the table
  3. Fibonacci tabulation
  4. Summary - Tabulation

3 LCS

  1. LCS definition
  2. DP table
  3. Backtracking the table
  4. Summary - LCS

4 Knapsack

  1. Knapsack problem
  2. 0/1 knapsack DP
  3. Decision table
  4. Summary - Knapsack

5 DP project

  1. Project: Overview
  2. Cost table
  3. DP solution
  4. Print the result

6 Matrix chain

  1. Multiplication order
  2. DP table
  3. Split point
  4. Summary - Matrix chain

7 Floyd-Warshall

  1. All pairs
  2. Triple loop
  3. Table update
  4. Summary - Floyd-Warshall

8 Dijkstra

  1. Single source
  2. Priority queue
  3. Relaxation
  4. Summary - Dijkstra

9 Bellman-Ford

  1. Negative weights
  2. Edge relaxation loop
  3. Negative cycle
  4. Summary - Bellman-Ford

10 Kruskal

  1. Minimum spanning tree
  2. Edge sorting
  3. Cycle check
  4. Summary - Kruskal

11 Prim

  1. Prim idea
  2. Priority queue
  3. Visited set
  4. Summary - Prim

12 Topological sort

  1. Dependency order
  2. DFS-based sort
  3. Kahn algorithm
  4. Summary - Topological sort

13 Union-find, trie, segment tree

  1. Union-find
  2. Trie
  3. Segment tree
  4. Summary - Advanced structures

14 Advanced final

  1. Challenge 1
  2. Challenge 2
  3. Challenge 3
  4. Challenge 4