Bottom Up vs TopDown

In Dynamic Programming, there are two main approaches to solving problems: Top-Down (Memoization) and Bottom-Up (Tabulation). Both achieve the same result—optimizing recursive algorithms—but they differ in implementation and execution flow.

1. Top-Down (Memoization)

This approach follows the natural recursive structure of the problem. You start with the large problem and break it down. To avoid redundant calculations, you store the result of each subproblem in a “memo” (usually a hash map or array).

• Logic: “To solve for N, I need N-1 and N-2. Let me check if I’ve already solved them.”
• Pros:
• Intuitive implementation (just add caching to recursion).
• Only solves subproblems that are strictly necessary.
• Cons:
• Recursion overhead (function call stack).
• Risk of Stack Overflow for deep recursion.

2. Bottom-Up (Tabulation)

This approach is iterative. You start by solving the smallest subproblems (base cases) and use their results to build up to the larger problem.

• Logic: “I know the answer for 0 and 1. I can use them to find 2. Then use 1 and 2 to find 3…”
• Pros:
• No recursion overhead (faster).
• No Stack Overflow risk.
• Easier to optimize space (see Space Optimization).
• Cons:
• May compute subproblems that aren’t needed for the final result (though rare in dense DP problems).
• Less intuitive for some complex state transitions.

3. Interactive Comparison: Order of Operations

Let’s visualize the Climbing Stairs problem (ways(n) = ways(n-1) + ways(n-2)).

• Top-Down: Notice how the recursion dives deep to the base cases before returning values.
• Bottom-Up: Notice how we simply fill the array from left to right.

[!TIP] Try it yourself: Click “Run Top-Down” then “Run Bottom-Up” to see the difference in execution flow.

Ready

4. Code Implementation: Climbing Stairs

Problem: You are climbing a staircase. It takes n steps to reach the top. Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Top-Down (Memoization)

// Java - Top-Down (Memoization)
import java.util.HashMap;
import java.util.Map;

class Solution {
  Map<Integer, Integer> memo = new HashMap<>();

  public int climbStairs(int n) {
    if (n <= 2) return n;

    if (memo.containsKey(n)) {
      return memo.get(n);
    }

    int result = climbStairs(n - 1) + climbStairs(n - 2);
    memo.put(n, result);
    return result;
  }
}

// Go - Top-Down (Memoization)
func climbStairs(n int) int {
  memo := make(map[int]int)

  var helper func(int) int
  helper = func(k int) int {
    if k <= 2 {
      return k
    }
    if val, exists := memo[k]; exists {
      return val
    }

    res := helper(k-1) + helper(k-2)
    memo[k] = res
    return res
  }

  return helper(n)
}

Bottom-Up (Tabulation)

// Java - Bottom-Up (Tabulation)
class Solution {
  public int climbStairs(int n) {
    if (n <= 2) return n;

    int[] dp = new int[n + 1];
    dp[1] = 1;
    dp[2] = 2;

    for (int i = 3; i <= n; i++) {
      dp[i] = dp[i - 1] + dp[i - 2];
    }

    return dp[n];
  }
}

// Go - Bottom-Up (Tabulation)
func climbStairs(n int) int {
  if n <= 2 {
    return n
  }

  dp := make([]int, n+1)
  dp[1] = 1
  dp[2] = 2

  for i := 3; i <= n; i++ {
    dp[i] = dp[i-1] + dp[i-2]
  }

  return dp[n]
}

5. When to use which?

Feature	Top-Down (Memoization)	Bottom-Up (Tabulation)
Mental Model	Recursive (start from N)	Iterative (start from base case)
Ease of Implementation	Often easier (direct translation of recurrence)	Requires determining iteration order
Speed	Slower (recursion overhead)	Faster (loops are cheap)
Space	O(N) stack space	O(N) table space (can often optimize to O(1))
Subproblems	Solves only needed subproblems	Solves all subproblems

---

6. Deep Dive Strategy Lab: Bottom Up Vs Topdown

Intuition Through Analogy

Think of this chapter like budget planning across months. The goal is not to memorize a fixed trick, but to repeatedly answer:

1. What is the bottleneck?
2. Which constraint dominates (time, memory, latency, correctness)?
3. Which representation makes the bottleneck easier to eliminate?