Memoization vs Tabulation in Dynamic Programming – Explained with Climbing Stairs

📖 Introduction

Dynamic Programming (DP) is a fundamental technique in solving problems with overlapping subproblems and optimal substructure. Two core strategies used in DP are:

• Memoization (Top-Down)

• Tabulation (Bottom-Up)

In this blog, we’ll break down both approaches using a common example: counting the number of ways to climb stairs — where at each step, you can climb either 1 or 2 steps.

---

🔁 Memoization (Top-Down Approach)

Memoization is like solving a problem by recursion, but with memory. We store the result of each subproblem the first time it’s solved, and re-use that result whenever the same subproblem appears again.

✅ How it works:

• Think recursively: “What’s the number of ways to climb n steps?”

• Save already-computed results in a dictionary or array.

• Use those saved results (cache) to avoid re-computation.

✨ Benefits:

• Easier to implement and reason about for recursive thinkers.

• Good when only a few subproblems are actually needed.

⚠️ Downsides:

• Can lead to stack overflow if recursion depth is high.

🧠 Memoization Code (Top-Down DP)

def count_ways_top_down(n, memo=None):
    if memo is None:
        memo = {}

    if n == 0 or n == 1:
        return 1   

    if n in memo:
        return memo[n]

    memo[n] = count_ways_top_down(n - 1, memo) + count_ways_top_down(n - 2, memo)
    return memo[n]

input = int(input("Enter a number: "))

print(f"ways to reach step {input} is: {count_ways_top_down(input)} ways")

---

📊 Tabulation (Bottom-Up Approach)

Tabulation is the opposite of memoization — it solves the smallest subproblems first and uses them to build up the answer for the full problem.

✅ How it works:

• Use an array dp where each element represents the solution to a subproblem.

• Start from the base cases and fill up to n.

✨ Benefits:

• Avoids recursion and stack overflow.

• Efficient in time and space if all subproblems are needed.

⚠️ Downsides:

• Sometimes less intuitive than recursive approaches.

• You must solve all subproblems, even if some aren’t needed.

🧠 Tabulation Code (Bottom-Up DP)

def count_ways(n):
    if n == 0 or n == 1:
        return 1

    dp = [0] * (n+1)
    dp[0] = 1
    dp[1] = 1

    for i in range(2,n+1):
        dp[i] = dp[i-1] + dp[i-2]

    return dp[n]

input = int(input("Enter a number: "))

print(f"ways to reach step {input} is: {count_ways(input)} ways")

---

🎯 Conclusion

Both memoization and tabulation are powerful tools in a dynamic programmer’s toolkit. Use memoization when your solution is naturally recursive, and use tabulation when you want full control over performance and stack usage.

Next time you tackle a DP problem, ask yourself:

“Do I want to go top-down or bottom-up?”

Choose wisely — both lead to the same destination.