What is tabulation?

Fill a table bottom-up to solve sub-problems.

What is tabulation?

Tabulation solves subproblems by filling a table bottom-up.

Loops replace recursion; each cell is a subproblem's result.

Tabulation is the bottom-up counterpart of memoization; no stack overflow risk.

Bottom-up approach

Tabulation solves the smallest subproblems first, then uses them to build larger ones.

There is no recursion; all computation happens in a loop.

This approach prevents stack overflow on deep recursion; it suits large n values.

Exercise Fibonacci tabulation

Write fib_tab(n). Compute Fibonacci with a table. Print 55 with print(fib_tab(10)).

Show example solution

def fib_tab(n):
    # Fibonacci tabulation
    if n <= 1:
        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]
print(fib_tab(10))

Test yourself

Which direction does tabulation work in?
- Top-down
- Bottom-up
- From sides
- Random
Show answer

Bottom-up — Bottom-up.
Table structure
```
dp = [0] * (____ + 1)
```
Show answer
```
dp = [0] * (n + 1)
```
What is tabulation: match the terms

tabulation

Bottom-up
table

Table
loop

Loop
no recursion

No recursion

Next lesson: Building the table

We Are Enhancing Your Experience

Cookie Preferences

Strictly Necessary Cookies

Analytical Cookies