Building the table
- Algorithms course
- Advanced
- Lesson 6/56
- 4 min
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.
Practice 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)).
Starter code
def trib_tab(n):
# Tribonacci tabulationSample 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))Expected output
6
Questions and answers
Review the lesson questions together with their answers. To test yourself, solve the lesson interactively.
1 Loop start
for i in range(____, n + 1):for i in range(2, n + 1):Explanation: 2 is right.
2 Building the table: match the terms
| Term | Meaning |
|---|---|
table |
Table |
cell |
Cell |
order |
Order |
dependency |
Dependency |
3 Why is the table filled in order?
- Dependencies are ready Correct answer
- Less memory
- It is faster
- No recursion needed
Explanation: Dependencies are ready.