Building the table

Fill a table array in order.

Building the table

The table holds subproblem results in order. Each cell is computed from previous cells.

The table size depends on the subproblem count; it can be one- or multi-dimensional.

The table structure depends on the problem; fibonacci needs only one dimension.

Ordered filling

Filling the table in order is essential; smaller indices first, then larger ones.

This ensures each cell's dependencies are ready; it gives a consistent result.

Wrong order produces incorrect results; the filling order is critical.

Exercise Tribonacci tabulation

Write trib_tab(n). Tribonacci: T(n) = T(n-1) + T(n-2) + T(n-3), T(0)=0, T(1)=0, T(2)=1. Print 6 with print(trib_tab(6)).

Show example solution

def trib_tab(n):
    # Tribonacci tabulation
    if n < 2:
        return 0
    if n == 2:
        return 1
    dp = [0] * (n + 1)
    dp[2] = 1
    for i in range(3, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3]
    return dp[n]
print(trib_tab(6))

Test yourself

Loop start

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

Show answer

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

Building the table: match the terms

table

Table
cell

Cell
order

Order
dependency

Dependency
Why is the table filled in order?
- Dependencies are ready
- Less memory
- It is faster
- No recursion needed
Show answer

Dependencies are ready — Dependencies are ready.

Next lesson: Fibonacci tabulation

We Are Enhancing Your Experience

Cookie Preferences

Strictly Necessary Cookies

Analytical Cookies