Summary - Tabulation

Compute Fibonacci with tabulation and print it in a mini task.

Summary - Tabulation

Tabulation is the loop-based DP method that fills a table bottom-up. No stack overflow risk.

In this mini task you will compute Fibonacci with tabulation and print it; combine all steps.

Tabulation is the bottom-up form of DP; it suits large problems.

Exercise Print Fibonacci

Write fib_tab_print(n). Compute Fibonacci with tabulation and print with print(). Output of fib_tab_print(20): 6765.

Show example solution

def fib_tab_print(n):
    # Print Fibonacci
    if n <= 1:
        print(n)
        return
    dp = [0] * (n + 1)
    dp[1] = 1
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    print(dp[n])
fib_tab_print(20)

Test yourself

Summary - Tabulation: match the terms

tabulation

Bottom-up
table

Table
loop

Loop
dp

DP

Loop start

for i in range(____, n + 1):

Show answer

for i in range(2, n + 1):

What is tabulation's biggest advantage?
- No recursion needed
- Less memory
- Faster
- No stack overflow
Show answer

No stack overflow — No stack overflow.

Next lesson: LCS definition

We Are Enhancing Your Experience

Cookie Preferences

Strictly Necessary Cookies

Analytical Cookies