Bottom-Up (Tabulation)
Overview
Bottom-Up (Tabulation) is the opposite approach to Memoization. Instead of starting at the massive, complex goal and recursing downwards, Tabulation starts at the absolute smallest base cases (dp[0], dp[1]) and uses an iterative for loop to build up the cache systematically until it reaches the final goal (dp[N]).
Because Tabulation eliminates recursion entirely, there is zero risk of StackOverflowError, and it executes slightly faster due to the lack of method-call overhead.
Furthermore, it allows for incredible Space Optimization. In Fibonacci, to calculate dp[i], you logically only need dp[i-1] and dp[i-2]. You can throw away the rest of the array and just use two integer variables. This drops the space complexity of a DP algorithm from O(N) to O(1), which is a massive engineering achievement.
Syntax
public class Tabulation {
public int climbStairsOptimized(int n) {
if (n <= 2) return n;
// Instead of an entire dp[] array of size N, we only keep track of the two
// previous states, optimizing space complexity to strict O(1).
int prev2 = 1; // Represents dp[i-2]
int prev1 = 2; // Represents dp[i-1]
for (int i = 3; i <= n; i++) {
int current = prev1 + prev2;
// Shift the window forward for the next iteration
prev2 = prev1;
prev1 = current;
}
return prev1;
}
}Common Pitfalls
- Harder to conceptualize. For complex branching problems, writing the logic iteratively is often significantly harder for developers to mentally map than writing it recursively.
- Wasteful computations on sparse graphs. Tabulation strictly calculates every single state from 0 to N. If you only actually needed 5 specific states to get the answer, you just wasted time computing N-5 useless states.
Interview Questions
Two major reasons: 1. It completely eliminates recursion, ensuring the app never crashes with a StackOverflow. 2. It frequently allows Space Optimization (dropping arrays in favor of a few variables), saving significant RAM.
Real-World Example
Production-grade algorithms where memory limits are strict. Embedded systems or high-frequency trading platforms cannot afford to allocate large arrays or deep call stacks. Using Tabulation with Space Optimization allows heavy math to run in O(1) auxiliary space safely.
// Trading algo optimized to O(1) space
public double calculateTrendPredictor(int days) {
double yesterdayData = 0.5;
double todayData = 0.8;
for (int i = 2; i < days; i++) {
double tomorrow = (todayData * 1.5) + (yesterdayData * 0.2);
yesterdayData = todayData;
todayData = tomorrow;
}
return todayData;
}Check Your Knowledge
Test your understanding of Bottom-Up (Tabulation) with these quick questions.