Chapter 60

Home

Refactoring: Bottom-up vs Top-down

Every DP problem can be solved top-down (memoisation) or bottom-up (tabulation). Which one should you write in a contest? The answer depends on the problem structure — here's a framework to decide.

Top-Down (Memoisation)

✅ Pros

  • • Intuitive — mirrors the recursive problem definition
  • • Only computes states that are actually needed
  • • Easy to add pruning or early termination

❌ Cons

  • • Recursion overhead and stack limit
  • • Hash map or sentinel-value checks add constant overhead
  • • Harder to space-optimise

C++ — top-down template

vector memo(N + 1, -1);

int dp(int state) {
    if (base_case(state)) return base_value;
    if (memo[state] != -1) return memo[state];

    int ans = INF;
    for (next_state : transitions(state))
        ans = max(ans, dp(next_state));  // or min, or sum

    return memo[state] = ans;
}

Bottom-Up (Tabulation)

✅ Pros

  • • No recursion — no stack overflow risk
  • • Easy to space-optimise (rolling arrays)
  • • Often faster in practice (contiguous memory access)

❌ Cons

  • • Computes all states even if some are unused
  • • Harder to derive from the problem statement
  • • Complex state transitions can be error-prone

C++ — bottom-up template

vector dp(N + 1, INF);
dp[base] = base_value;

for (int state = base + 1; state <= N; state++)
    for (prev : transitions_to(state))
        dp[state] = max(dp[state], dp[prev]);

Decision Framework

Use top-down when:

The state space is large but sparse (few states actually reached). The recurrence is easier to express recursively. You need early-exit pruning.

Use bottom-up when:

All states must be computed. You need space optimisation. N is large and recursion depth is a concern.

In a contest:

Write whichever you're more comfortable with first. If it times out or hits memory limits, refactor. Both approaches have the same time complexity — the constant factors and memory usage differ.

Key Takeaways

Practice