Top-Down vs Bottom-Up

Think of DP states as nodes in a directed graph, where each node points to the states it depends on. Top-down starts at the answer node and recursively visits dependencies on demand. Bottom-up starts from base nodes and visits states in an order that eventually reaches the answer.

Because the recurrence is usually the same, the asymptotic time is often identical: number of reachable states times transition work. The practical differences come from how many states are reached and how expensive each state evaluation is.

Top-down uses the call stack. That is fine for shallow trees but risky for deep linear chains, large grids, or recurrences where n can be very large. Java does not optimize tail calls, so deep memoized recursion can fail even when the algorithmic complexity is correct.

Bottom-up uses explicit loops and heap-allocated tables, so it avoids call-stack risk. In production-quality Java interviews, this is a strong reason to present bottom-up as the final form for straightforward one-dimensional or two-dimensional DPs.

Top-down computes only states reachable from the original query. If pruning removes large parts of the state space, memoization can be faster and simpler. Word Break is a good example: many starting indices may never be explored if earlier checks fail.

Bottom-up often scans the whole table. That predictability can improve locality and reduce overhead, especially with primitive arrays. Function calls, recursion frames, and map lookups can make top-down slower even when both approaches have the same big-O bound.

Bottom-up usually makes memory dependencies visible. If row i depends only on row i - 1, a rolling array is natural. If dp[i] depends only on two previous values, two variables are enough.

Top-down caches are harder to compress because recursive calls may revisit older states in less predictable order. You can still reduce memory in some top-down designs, but most interview space optimizations are clearer after converting to tabulation.

Start top-down when you need clarity, the state space is sparse, or the recurrence is irregular. Convert to bottom-up when the dependency order is obvious, stack depth is a concern, or space optimization is expected.

A strong interview answer can mention both: derive with memoization for intuition, then implement bottom-up for reliability and better constants. That sequence shows both reasoning and engineering judgment.