Tabulation
Tabulation is the bottom-up approach to dynamic programming. Rather than starting from the target problem and recursing toward base cases, tabulation start...
Bottom-Up Dynamic Programming
Tabulation is the bottom-up approach to dynamic programming. Rather than starting from the target problem and recursing toward base cases, tabulation starts from the smallest sub-problems (base cases) and iteratively builds solutions toward the full problem. Each cell in a DP table is filled using only previously computed cells, eliminating any need for recursion.
The process: identify the state space (e.g., all values of i from 0 to n and j from 0 to W), define the base cases (typically when one index is zero), and then fill the table in an order that ensures all dependencies of dp[i][j] are computed before dp[i][j] itself. For most 1D problems this means left-to-right; for 2D problems it usually means row by row.
A worked example: the classic staircase problem. You can climb 1 or 2 steps at a time; how many ways are there to reach step n? Base cases: dp[0] = 1 (one way to stand at ground), dp[1] = 1. Recurrence: dp[i] = dp[i-1] + dp[i-2]. Fill dp[2] = dp[1] + dp[0] = 2, dp[3] = 3, dp[4] = 5, ... The pattern is Fibonacci. Time complexity O(n), space O(n) (or O(1) with rolling variables).
Determining fill order is the core challenge of tabulation. Draw a dependency graph: dp[i][j] depends on which cells? If it depends on dp[i-1][j] and dp[i][j-1], fill left-to-right within each row, processing rows top-to-bottom. If dependencies are more complex (e.g., dp[i][j] depends on dp[k][m] for k < i and m > j), you need to think carefully about iteration order.
Interview tip: Sketch the DP table on paper or whiteboard before coding. Drawing three to four cells and showing their values and dependencies concretely demonstrates understanding and helps you catch fill-order bugs before they appear in code.
Space Optimization with Rolling Arrays
Many DP problems require only a small window of previously computed rows or entries to compute the current one. When dp[i][j] depends only on dp[i-1][j] and dp[i][j-1], you need only the previous row — not the entire table. This observation allows you to reduce O(n*m) space to O(m) by keeping only two rows: the previous row and the current row being filled.
The rolling array technique replaces the 2D table dp[n][m] with two 1D arrays prev[m] and curr[m]. For each row i, compute curr[j] from prev[j] and curr[j-1], then at the end of the row copy curr into prev and reuse curr for the next row. This halves space immediately, and in many problems you can reduce further to a single array updated in place.
For the knapsack problem, dp[i][w] = max(dp[i-1][w], dp[i-1][w - weight[i]] + value[i]). With a rolling array: use a single 1D array dp[W+1], but iterate w from W down to weight[i]. Iterating backwards ensures dp[w - weight[i]] still holds the previous row's value when you read it. If you iterate forwards, dp[w - weight[i]] would already be updated (using item i twice), giving the unbounded knapsack answer instead.
This direction-of-iteration distinction is subtle and a common interview trap. For problems like LCS where dp[i][j] depends on dp[i-1][j-1] (diagonal), you need to save the diagonal value before overwriting it — store it in a temporary variable at the start of each inner loop iteration.
Interview tip: Space-optimize only after demonstrating the correct O(n*m) solution. Say "I can reduce space from O(n*m) to O(m) by observing that row i depends only on row i-1." Optimizing prematurely can introduce subtle direction bugs, and interviewers appreciate seeing you optimize deliberately rather than by accident.
Filling Order and Dependency Analysis
Correctly determining the fill order for a DP table is the most mechanically demanding part of bottom-up DP. The rule is simple: compute dp[i][j] only after all cells it depends on have been computed. Violating this order produces incorrect results without any error message, making fill-order bugs especially insidious.
For 1D problems where dp[i] depends on dp[i-1] or dp[i-2], filling left-to-right is straightforward. For 2D problems, the dependency structure determines the iteration pattern. If dp[i][j] depends on dp[i-1][j], dp[i][j-1], and dp[i-1][j-1] (as in LCS), filling row by row left-to-right works because all three predecessors are already computed.
More complex dependency structures require careful thought. Interval DP problems have states dp[i][j] representing sub-problems on the interval [i, j], and dp[i][j] depends on dp[i][k] and dp[k+1][j] for i <= k < j. Here, all shorter intervals must be computed before longer ones. The correct fill order is: for each length l from 2 to n, for each starting index i from 1 to n-l+1, set j = i + l - 1, then compute dp[i][j]. This ensures all sub-intervals of [i, j] are computed first.
Matrix chain multiplication and optimal binary search trees both use interval DP with this fill order. Getting the order wrong — for example, iterating i from 1 to n for each j from i to n — computes intervals in the wrong order and uses uninitialized values.
Interview tip: Before implementing, verbally walk through two concrete cells and state which cells they depend on. Then describe your iteration order and confirm it satisfies those dependencies. This explicit dependency analysis catches order bugs before you write a single line of code.