A Universal Rule to Convert Memoization DP into Tabulation (Works for Every Problem)

Dynamic Programming often feels hard not because the problems are complex, but because people don’t have a fixed process. If you already know memoization (top-down DP), converting it to tabulation (bottom-up DP) should be mechanical — not something you “figure out again” every time.

This article gives you a universal, repeatable rule that works for all DP problems.

Why Memo → Tabulation feels confusing

In memoization:

• You write recursion naturally
• The system decides the order of execution

In tabulation:

• You must decide the order yourself
• A wrong loop order breaks everything

So the real challenge is loop order, not DP itself.

The Core Idea (Read This Twice)

Tabulation is just the memo table filled manually in dependency order instead of recursion order.

That’s it. Everything below is just applying this idea correctly.

The Universal 6-Step Rule

Follow these steps in order, for every DP problem.

Step 1: Identify the DP state (most important)

Look at the memoized function parameters.

Example:

f(i, w)

This immediately means:

dp[i][w]

Rule: 👉 Each function parameter becomes one DP dimension.

Step 2: Decide DP table size

Look at the range of each parameter.

Example:

• i → 0 to n
• w → 0 to W

DP table:

dp[n+1][W+1]

Bonus: This step already gives you:

• Time complexity: O(n × W)
• Space complexity: O(n × W)

Step 3: Write the recurrence (copy-paste logic)

Take the memo recurrence and remove recursion syntax.

Memo:

f(i, w) = max(
    f(i+1, w),
    val[i] + f(i+1, w-wt[i])
)

Tabulation:

dp[i][w] = max(
    dp[i+1][w],
    val[i] + dp[i+1][w-wt[i]]
)

Rule: 👉 Logic never changes. Only recursion becomes table lookup.

Step 4: Convert base cases into table initialization

Memo base case:

if (i == n || w == 0) return 0;

Tabulation:

dp[n][w] = 0   // for all w
dp[i][0] = 0   // for all i

Rule: 👉 Every return base case becomes a pre-filled DP cell.

Step 5: Decide loop order (this is the key)

Golden Rule:

Fill the DP table in the reverse direction of recursion dependency.

Examples:

Memo DependencyLoop Directionf(i) → f(i+1)i = n-1 → 0f(i) → f(i-1)i = 1 → nf(i,j) → f(i-1,j-1)forward loopsf(i,j) → f(i+1,j+1)reverse loops

Think like this:

Children must be filled before parents.

Step 6: Final answer location

Memo call:

f(start_state)

Tabulation answer:

dp[start_state]

Example:

return dp[0][W];

One-Sentence Mental Model

Memoization asks “what is the answer?” Tabulation answers the same question, just in the correct order.

Why This Works for Every DP Problem

This exact process works for:

• Knapsack
• LCS / Edit Distance
• Grid DP
• Subset Sum
• LIS
• DP on strings

Because every DP problem is just states + dependencies.