Definition
Tabulation is the bottom-up form of dynamic programming.
- Base cases are filled first in the table.
- Iteration order ensures every cell's dependencies are already computed when it is reached.
- No recursion means no call-stack risk and no overhead from function calls.
- Space optimization is often straightforward because only the most recent rows or values are needed.
- Asymptotic cost matches memoization but avoids recursion overhead and stack limits.
The National Bank of India builds a running end-of-day balance ledger starting from the opening balance and adding each day's transactions in order. Every day's figure relies only on days already posted, so the team never has to look ahead or recurse. This is tabulation: fill forward from what you know.
Understanding the Concepts
What is Tabulation?
Tabulation is the bottom-up approach to dynamic programming. Instead of recursing from the goal down to base cases and caching results on the way back up, we start from the base cases and fill a table iteratively, choosing a fill order where every subproblem's dependencies are already solved.
At National Bank of India, Rajesh computes daily running balances starting from the opening balance, adding each day's net transactions in order.
package com.bank.service;
import java.math.BigDecimal;
public class RunningBalance {
public static BigDecimal[] computeBalances(BigDecimal opening, BigDecimal[] dailyNet) {
int days = dailyNet.length;
BigDecimal[] balance = new BigDecimal[days + 1];
balance[0] = opening; // base case
for (int d = 1; d <= days; d++) {
balance[d] = balance[d - 1].add(dailyNet[d - 1]); // fill forward
}
return balance;
}
public static void main(String[] args) {
BigDecimal opening = new BigDecimal("100000");
BigDecimal[] daily = {
new BigDecimal("5000"), new BigDecimal("-2000"),
new BigDecimal("10000"), new BigDecimal("-3000")
};
BigDecimal[] balances = computeBalances(opening, daily);
for (int i = 0; i < balances.length; i++) {
System.out.println("Day " + i + ": " + balances[i]);
}
}
}
Day 0: 100000
Day 1: 105000
Day 2: 103000
Day 3: 113000
Day 4: 110000
How Does Tabulation Differ from Memoization?
Memoization is top-down: you write the natural recursion from the goal and cache results. Tabulation is bottom-up: you identify base cases and fill forward. Both have the same asymptotic complexity, but they differ in practical aspects.
| Aspect | Memoization (Top-Down) | Tabulation (Bottom-Up) |
|---|---|---|
| Direction | Goal to base cases | Base cases to goal |
| Mechanism | Recursion + cache | Iteration + table |
| Stack usage | O(depth) call stack | No recursion |
| Overflow risk | StackOverflowError for deep problems | None |
| Space optimization | Harder (cache is sparse) | Easy (keep recent rows) |
| State coverage | Only visited states | All states filled |
| Code style | Natural recursive formulation | Requires explicit fill order |
package com.bank.core;
public class FibComparison {
// Memoization (top-down)
public static long fibMemo(int n, long[] memo) {
if (n <= 1) return n;
if (memo[n] != 0) return memo[n];
memo[n] = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
return memo[n];
}
// Tabulation (bottom-up)
public static long fibTab(int n) {
if (n <= 1) return n;
long[] dp = new long[n + 1];
dp[0] = 0; dp[1] = 1;
for (int i = 2; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
public static void main(String[] args) {
System.out.println("Memo fib(10): " + fibMemo(10, new long[11]));
System.out.println("Tab fib(10): " + fibTab(10));
}
}
Memo fib(10): 55
Tab fib(10): 55
How Do You Choose the Fill Order?
The fill order must ensure that when you compute a cell, all cells it depends on are already filled. For 1D problems this is usually left-to-right. For 2D problems it depends on the recurrence: sometimes row by row, sometimes by diagonal, sometimes by interval length.
package com.bank.core;
public class FillOrderExamples {
// 1D: dp[i] depends on dp[i-1], dp[i-2]
// -> fill left to right
// 2D grid path: dp[i][j] depends on dp[i-1][j], dp[i][j-1]
// -> fill top-to-bottom, left-to-right
// Interval DP: dp[i][j] depends on dp[i][k], dp[k][j] for i < k < j
// -> fill by increasing interval length (j - i)
// Knapsack: dp[i][w] depends on dp[i-1][w], dp[i-1][w-weight]
// -> fill row by row, left-to-right
}
What About Space Optimization?
When each cell depends only on a few recent cells, we can replace the full table with rolling variables. For Fibonacci, two variables suffice. For 2D knapsack, one row suffices with the correct sweep direction.
package com.bank.core;
public class FibSpaceOptimized {
public static long fib(int n) {
if (n <= 1) return n;
long prev2 = 0, prev1 = 1;
for (int i = 2; i <= n; i++) {
long curr = prev1 + prev2;
prev2 = prev1;
prev1 = curr;
}
return prev1;
}
public static void main(String[] args) {
System.out.println("fib(50) = " + fib(50)); // O(1) space!
}
}
fib(50) = 12586269025
When Should You Use Tabulation Over Memoization?
Use tabulation when:
- The problem could have very deep recursion that risks StackOverflowError.
- You need space optimization (rolling variables).
- All subproblems must be solved (the state space is dense).
Use memoization when:
- Only a small fraction of the state space is reachable.
- The recursive formulation is more natural and easier to write.
- You want to avoid working out the correct fill order.
package com.bank.core;
public class TabulationVsMemoization {
// Tabulation advantages:
// No stack overflow, easy space optimization, no overhead per call
// Memoization advantages:
// Skips unreachable states, natural recursive code, easier to write
}
What Are Common Tabulation Patterns?
The most common tabulation patterns are: 1D linear (Fibonacci, climbing stairs), 1D knapsack (coin change, subset sum), 2D grid (unique paths, minimum path sum), 2D string (LCS, edit distance), and interval (burst balloons, matrix chain).
package com.bank.core;
public class TabulationPatterns {
// 1D Linear: dp[i] = f(dp[i-1], dp[i-2])
// Examples: Fibonacci, Climbing Stairs, House Robber
// 1D Knapsack: dp[w] = f(dp[w], dp[w-weight])
// Examples: Coin Change, Subset Sum, 0/1 Knapsack
// 2D Grid: dp[i][j] = f(dp[i-1][j], dp[i][j-1])
// Examples: Unique Paths, Minimum Path Sum
// 2D String: dp[i][j] = f(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])
// Examples: LCS, Edit Distance, Regex Matching
// Interval: dp[i][j] = f(dp[i][k], dp[k][j]) for all k
// Examples: Burst Balloons, Matrix Chain, Palindrome Partition
}
What Are Common Mistakes in Tabulation?
The first mistake is getting the fill order wrong so that a cell is computed before its dependencies are ready. The second is off-by-one errors in array sizing or loop bounds.
package com.bank.core;
public class TabulationMistakes {
// WRONG: array too small
// int[] dp = new int[n]; // needs dp[n], so size should be n+1
// CORRECT
// int[] dp = new int[n + 1];
// WRONG: fill order for interval DP
// for (int i = 0; i < n; i++)
// for (int j = i+1; j < n; j++) // dp[i][j] needs dp[i][k] for k > i
// -> correct order is by length: for (int len = 2; len <= n; len++)
}
What Are Common Interview Follow-Up Questions?
Interviewers commonly ask:
- Convert a memoized solution to tabulation: identify the base cases and fill order.
- Optimize the space: identify which previous cells each entry depends on.
- When is memoization better? When the state space is sparse.
- Give an example of a problem where tabulation is essential: very deep recursion like Fibonacci of 100,000.
package com.bank.core;
public class TabulationFollowUp {
// Memoized fib(100000) would stack overflow
// Tabulated fib(100000) works fine with O(1) space
// That is why tabulation matters for large inputs
}
Visual Overview
Memoization (Top-Down) vs Tabulation (Bottom-Up):
MEMOIZATION: TABULATION:
┌────────────────┐ ┌────────────────┐
│ Start at GOAL │ │ Start at BASE │
│ │ │ │ │ │
│ ▼ │ │ ▼ │
│ Recurse down │ │ Fill forward │
│ │ │ │ │ │
│ ▼ │ │ ▼ │
│ Hit BASE case │ │ Reach GOAL │
│ │ │ │ │
│ ▼ │ │ No recursion! │
│ Cache on way up │ │ No stack risk! │
└────────────────┘ └────────────────┘
Fibonacci Tabulation:
┌───┬───┬───┬───┬───┬───┬───┐
│ 0 │ 1 │ 1 │ 2 │ 3 │ 5 │ 8 │
└───┴───┴───┴───┴───┴───┴───┘
0 1 2 3 4 5 6
──────────────────────────>
Fill left to right
Key Takeaway
Tabulation is the bottom-up way of doing dynamic programming, and I contrast it directly with memoization to show I understand both. Memoization is top-down: I write the natural recursion from the goal toward the base cases and let a cache remember each result so repeated subproblems are not recomputed. Tabulation flips the direction: I start from the base cases and fill a table outward, choosing an iteration order such that by the time I compute any cell, every cell it depends on is already filled.
The practical advantages of tabulation are that it uses no recursion, so there is no risk of a stack overflow on large inputs, and it makes space optimization obvious. Once I see that each cell depends only on a couple of recent cells, I can throw away the rest of the table and keep rolling variables. The main discipline it demands is working out the correct iteration order up front.
At the National Bank of India I used tabulation to compute daily running balances, where each day's closing balance depends only on the previous day's closing balance plus that day's net transactions. Filling the ledger left to right from the opening balance satisfied every dependency naturally and needed no recursion.
The choice between tabulation and memoization is not about correctness but about practical tradeoffs: tabulation avoids stack overflow and enables space optimization, while memoization can skip unreachable states and is often easier to write.
Remember one sentence: tabulation fills the DP table from base cases forward in dependency order, with no recursion and easy space optimization.
---