DP Memoisation vs Tabulation — Top-Down vs Bottom-Up, and When Each Wins

Every DP problem has two shapes: top-down (memoisation) and bottom-up (tabulation). Same recurrence, same complexity, same output — but different code, different space profile, and different interview vibes. Memoisation reads like the recursion the problem started as; tabulation reads like a well-oiled loop. This post is the tie-breaker: when each wins, when the choice matters, and how to convert between them without introducing bugs.

The verdict

Memoisation (top-down). Write the recurrence naturally; wrap it in a cache. Cleaner code for tree-shaped recurrences and problems where the state space is sparse.

Tabulation (bottom-up). Fill a table in dependency order. Cache-friendly, sometimes lets you drop dimensions (rolling arrays), and avoids the recursion-stack cost.

Same time complexity: O(states × transition_cost). Same worst-case space if you keep the full table. The trade-off is code shape, recursion-stack cost, and whether you can shrink space with a rolling optimisation.

When to reach for memoisation (top-down)

• Recurrence is naturally tree-shaped (LC 337 House Robber III on a binary tree, LC 894 All Possible Full Binary Trees). Writing it recursively matches the structure; tabulation would need to serialise the tree first.
• State space is sparse — you don't actually visit every possible state. Tabulation over 10⁶ states you never touch is wasteful; memoisation only fills the ones you visit.
• You want the code to read like the mathematical recurrence. f(n) = f(n-1) + f(n-2) becomes seven lines with @cache. Elegant on a whiteboard.
• You're prototyping and the state definition is uncertain. Memoisation lets you iterate on the recurrence quickly; if the state changes, the cache adapts.

When to reach for tabulation (bottom-up)

• You want to apply a rolling-array space optimisation. The recurrence only reads the last k rows — keep just those k rows for O(width) space instead of O(n × width). See the space complexity post.
• State space is dense — you visit every state anyway. Tabulation's slight constant-factor edge shows up.
• Recursion depth would exceed language limits. Python's default limit is ~1000; deep DPs like edit distance on a 10⁵-length string blow the stack recursively.
• The interviewer explicitly asks for iterative. They usually mean "prove you can do it without recursion".
• Cache locality matters for the wall-clock time. Tabulation with a fixed-size array is friendlier to modern CPUs than a hash-map-backed memo.

Side by side

Worked example — LC 322 Coin Change

Fewest coins to make amount.

Memoisation

from functools import cache

def coinChange(coins, amount):
    @cache
    def f(a):
        if a == 0:
            return 0
        if a < 0:
            return float('inf')
        return min(f(a - c) for c in coins) + 1
    ans = f(amount)
    return ans if ans != float('inf') else -1

Recurrence, cache, done. Reads like the math. Recursion depth up to amount — fine for LeetCode's typical amount ≤ 10⁴, but on adversarial inputs you'd bump sys.setrecursionlimit.

Tabulation

def coinChange(coins, amount):
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0
    for a in range(1, amount + 1):
        for c in coins:
            if c <= a:
                dp[a] = min(dp[a], dp[a - c] + 1)
    return dp[amount] if dp[amount] != float('inf') else -1

Same complexity, no recursion, no cache library. The iteration order (a from 1 upward) is what "bottom-up" means — every state's dependencies are already computed by the time we visit it.

The tabulated version doesn't win on space here (both are O(amount)), but it opens the door: if a follow-up asks for "return the actual coins used", the tabulation trivially back-traces through the dp array. The memoisation needs a second pass.

Rolling-array optimisation — the tabulation edge

Consider LC 1143 Longest Common Subsequence. Full tabulation:

def longestCommonSubsequence(text1, text2):
    n, m = len(text1), len(text2)
    dp = [[0] * (m + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if text1[i - 1] == text2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    return dp[n][m]

O(n · m) time, O(n · m) space. The recurrence only reads row i - 1 and row i — keep just two rows:

def longestCommonSubsequence(text1, text2):
    n, m = len(text1), len(text2)
    prev = [0] * (m + 1)
    for i in range(1, n + 1):
        curr = [0] * (m + 1)
        for j in range(1, m + 1):
            if text1[i - 1] == text2[j - 1]:
                curr[j] = prev[j - 1] + 1
            else:
                curr[j] = max(prev[j], curr[j - 1])
        prev = curr
    return prev[m]

Same time, O(m) space. This drop is trivial with tabulation and hard to replicate cleanly with memoisation — the memoisation cache has to hold every visited state, and there's no natural way to discard entries.

Conversion recipe

Top-down → bottom-up.

1. Identify the state shape from the memoised function's parameters.
2. Identify the base cases from the top of the function.
3. Determine the correct fill order — dependencies must come first. If f(i) depends on f(i - 1), iterate i from small to large.
4. Replace the recursive calls with array lookups.

Bottom-up → top-down.

1. The recurrence written in the loop becomes the function body.
2. Base cases become early-return conditions.
3. Add @cache or @lru_cache decorator.
4. Return the recursive call with the initial arguments.

For most DP problems, one direction is more natural than the other. LC 322 goes cleanly both ways; LC 1143 is easier to space-optimise as tabulation; LC 337 (House Robber III on a binary tree) is easier top-down because the state naturally lives on tree nodes.

Bottom line

Ask: do I need to optimise space with a rolling array?

• Yes — tabulation. The natural fill order lets you keep only the last k rows.
• No, and the recurrence is naturally recursive or tree-shaped — memoisation. Cleaner code with @cache, and no rolling-array benefit anyway.
• No, and the state space is sparse — memoisation. You only fill states you visit.
• No, and depth would blow the stack — tabulation. No recursion.

Both approaches are the same DP under the hood. Getting comfortable with both — and knowing when to convert — is what separates candidates who've memorised one style from those who understand the underlying recurrence.

For the state-definition step that comes before this decision, see the DP state-definition post. For the O(states × transition) complexity accounting both approaches share, see the Big-O cheat sheet. For the rolling-array space claim, see the space complexity post.