Tabulation (Bottom-Up DP)
Tabulation computes DP states in an explicit dependency order, replacing recursive requests with loops. Using the same Fibonacci definition as memoization isolates what changes: the state and recurrence remain identical, while the execution schedule becomes iterative. Learning to derive this order is essential for grids, knapsack layers, intervals and graph DP.
Prerequisites: Memoization; loops; dependency graphs.
Build the idea
Recognize the repeated subproblems
The uncached Fibonacci tree repeats indices, and memoization fixes repetition through a lookup. Bottom-up DP instead plans to compute each needed index once. When states can be listed cheaply and most are reachable anyway, an explicit loop avoids function overhead and deep recursion. A loop is not automatically DP; its entries must still represent well-defined repeated subproblems.
Define the state
dp[i] is the exact i-th Fibonacci number. The full vector preserves all earlier values, making dependencies easy to inspect. No call-specific information belongs in the state. This is the same state as the memoized version, so converting approaches does not require inventing a different recurrence or altering the mathematical answer.
Derive the transition
For i≥2, set dp[i]=dp[i−1]+dp[i−2]. Both dependencies are one or two positions smaller. Each value combines those two already computed states exactly once. Unlike an optimization minimum, there is no choice between transitions here; both terms are part of the Fibonacci definition. Other counting recurrences need a disjoint-case argument before summing.
Base cases and computation order
Initialize dp[0]=0 and, only if n≥1, dp[1]=1. Fill i=2…n. This conditional second base avoids out-of-bounds writing for n=0. The array starts with zero values, but only the explicitly justified bases and completed earlier indices are meaningful. An increasing loop is a topological order of this simple acyclic state graph.
Correctness and invariant
Before iteration i, every dp[0…i−1] matches its Fibonacci definition. The two required entries are therefore correct, and assigning their sum establishes the invariant for i. This is structural induction made executable as a loop. Iterating downward would read uncomputed states and break the invariant, even though the formula text looked unchanged.
Work the example
For n=6, successive stored values are 0,1,1,2,3,5,8. State 6 reads 5 and 3 from indices 5 and 4. The sample uses n=10 and prints 55. Top-down and bottom-up outputs match; the difference is how the computation is scheduled and how much stack it requires.
i 0 1 2 3 4 5 6 dp[i] 0 1 1 2 3 5 8
C++17 implementation
This is a complete program. Compile with C++17 and enter the input described below.
#include<iostream>
#include<vector>
int main(){
int n;
std::cin>>n;
std::vector<long long>dp(n+1);
dp[0]=0;
if(n>=1){
dp[1]=1;
}
for(int i=2;i<=n;++i){
dp[i]=dp[i-1]+dp[i-2]; // Increasing index is a dependency order.
}
std::cout<<dp[n]<<'\n';
}
Complexity analysis
O(n) states and two reads per nonbase state give O(n) time. O(n) vector storage and O(1) call-stack usage. Keeping just the last two values reduces auxiliary DP memory to O(1) if the complete table is not needed.
Example input and output
Read n in 0..90. Print exact F(n).
Input
10
Output
55
For n=6, successive stored values are 0,1,1,2,3,5,8. State 6 reads 5 and 3 from indices 5 and 4. The sample uses n=10 and prints 55. Top-down and bottom-up outputs match; the difference is how the computation is scheduled and how much stack it requires.
Practical applications
Use tabulation for dense state spaces with a clear index order and when recursion depth is a concern. A DAG’s topological order generalizes this loop; interval DP uses increasing lengths rather than increasing endpoints alone.
Check your understanding
Why is increasing i valid here?
Put it into practice
Implement a two-variable Fibonacci version and compare all n≤90.
Show a hint
Do not overwrite the older value before both transition inputs have been used.