Memoization to Tabulation (Bottom-Up DP)

From Top-Down to Bottom-Up: A Shift in Perspective

Before diving into code, let's clarify the conceptual difference between the two DP approaches.

• Memoization (Top-Down): You start by calling your function for the main problem (e.g., fib(n)). The function then makes recursive calls for smaller subproblems (fib(n-1), fib(n-2)), and so on, until it hits a base case. It solves subproblems as they are needed and stores the results. It's a "pull" model—the main problem pulls the answers it needs from subproblems.

• Tabulation (Bottom-Up): You start by solving the smallest, simplest subproblems (the base cases). Then, you iteratively use those results to solve slightly larger subproblems, until you have built your way up to the solution for the main problem. It's a "push" model—the base cases push their solutions upward.

The Conversion Process: A 5-Step Guide

Converting a memoized solution to a tabulated one can be done systematically. Let's use the familiar Fibonacci problem as our initial guide.

Here's the memoized recursive solution for fib(n):

def fib_memo(n, memo):
    if n <= 1:
        return n
    if n in memo:
        return memo[n]
    
    memo[n] = fib_memo(n - 1, memo) + fib_memo(n - 2, memo)
    return memo[n]

Now, let's convert this step-by-step.

Step 1: Define the DP State and Array

Your memoized function's parameters define the "state." Here, fib_memo(n) has one parameter, n, so our state is one-dimensional. We will create a 1D array (our "DP table") to store the results of subproblems. The size of this array should accommodate all possible states, from the base case up to the target n.

• Action: Create a dp array of size n + 1. dp[i] will store the value of fib(i).

Step 2: Initialize Base Cases

Look at the base cases of your recursive function. These are the smallest subproblems you can solve directly.

• Recursive Base Cases: if n <= 1: return n
• Action: Translate these directly into your dp array.
  • dp[0] = 0
  • dp[1] = 1

Step 3: Determine the Iteration Order

This is a critical step. To calculate dp[i], the values it depends on must have already been computed. Look at the recurrence relation:

• Recurrence: fib(n) = fib(n-1) + fib(n-2)
• Dependency: To calculate dp[i], you need dp[i-1] and dp[i-2].
• Action: This dependency tells us we must iterate from smaller indices to larger ones. We will use a loop that starts after our base cases and goes up to n. for i from 2 to n.

Step 4: Translate the Recurrence Relation into Loop Logic

Take the heart of your recursive function—the recurrence relation—and place it inside the loop. Replace the recursive calls with lookups into your dp array.

• Recursive Logic: memo[n] = fib_memo(n - 1, memo) + fib_memo(n - 2, memo)
• Action: Inside the loop, this becomes dp[i] = dp[i-1] + dp[i-2].

Step 5: Identify the Final Answer

The answer to the original problem is the value you were trying to compute in the first place, which is now the last entry computed in your dp array.

• Action: The final answer is dp[n].

Putting it all together, the tabulated solution looks like this:

def fib_tabulation(n):
    if n <= 1:
        return n
    
    # Step 1: Create DP array
    dp = [0] * (n + 1)
    
    # Step 2: Initialize base cases
    dp[1] = 1 
    
    # Step 3 & 4: Iterate and apply recurrence
    for i in range(2, n + 1):
        dp[i] = dp[i-1] + dp[i-2]
        
    # Step 5: Return final answer
    return dp[n]

To see this process explained with code, the following video is an excellent guide.

Case Study: The House Robber Problem

Now let's apply this systematic process to a common interview problem: House Robber. We'll use the version from the hellointerview.com article you saw previously.

Problem: Given an array of treasures in houses, find the maximum amount you can collect without robbing two adjacent houses.

The article provides a full walkthrough from identifying the recurrence relation to the final optimized solution. Let's focus on the key conversion step.

Let's break down the conversion for House Robber using our 5-step process:

1. State and Array: The recursive helper is rob_helper(i), where i is the number of houses considered. So, we need a 1D array, dp, of size len(treasure) + 1. dp[i] will store the max treasure from the first i houses.
2. Base Cases:
   • rob_helper(0) returns 0 -> dp[0] = 0
   • rob_helper(1) returns treasure[0] -> dp[1] = treasure[0]
3. Iteration Order: The recurrence is dp[i] = max(dp[i-1], dp[i-2] + treasure[i-1]). The calculation for i depends on i-1 and i-2, so we must iterate from 2 up to len(treasure).
4. Loop Logic: The recurrence relation max(rob_helper(i-1), rob_helper(i-2) + treasure[i-1]) becomes dp[i] = max(dp[i-1], dp[i-2] + treasure[i-1]) inside the loop.
5. Final Answer: The solution for all houses is dp[len(treasure)].

This systematic conversion is a powerful and repeatable pattern for your interviews.

def climb_memo(n, memo):
    if n <= 1:
        return 1
    if n in memo:
        return memo[n]
    
    memo[n] = climb_memo(n - 1, memo) + climb_memo(n - 2, memo)
    return memo[n]

def climb_tabulation(n):
    if n <= 1:
        return 1
    
    # 1. State and Array: State is `n`, so we need a 1D array of size n+1.
    dp = [0] * (n + 1)
    
    # 2. Base Cases:
    # From `if n <= 1: return 1`, we get:
    dp[0] = 1 # 1 way to be at step 0 (do nothing)
    dp[1] = 1 # 1 way to reach step 1 (take one step)
    
    # 3. Iteration Order: `dp[i]` depends on `dp[i-1]` and `dp[i-2]`, so iterate up.
    # 4. Loop Logic: Translate the recurrence.
    for i in range(2, n + 1):
        dp[i] = dp[i-1] + dp[i-2]
        
    # 5. Final Answer: The number of ways to reach stair `n`.
    return dp[n]

An Important Follow-Up: Space Optimization

Once you have a working tabulated solution, a common interview follow-up is: "Can you optimize the space complexity?"

Look at the recurrence for Fibonacci or House Robber again:
dp[i] = ... dp[i-1] ... dp[i-2] ...

To compute the value for dp[i], you only need the two previous values. You don't need dp[i-3], dp[i-4], etc. This means we don't have to store the entire dp array. We can achieve the same result with just a few variables.

This optimization turns our O(n) space solution into an O(1) space solution, which is a significant improvement that interviewers love to see.

For House Robber, the optimized solution looks like this:

def rob_optimized(treasure):
    if not treasure:
        return 0
    
    # prev corresponds to dp[i-2], curr corresponds to dp[i-1]
    prev, curr = 0, 0 
    
    for t in treasure:
        # dp[i] = max(dp[i-1], dp[i-2] + treasure[i-1])
        # The new 'curr' will be the new dp[i-1] for the next iteration
        temp = max(curr, prev + t)
        prev = curr
        curr = temp
        
    return curr

Note: This implementation is slightly different from the one in the HelloInterview article to align with iterating through the treasures directly, but the logic of storing only two previous values is the same.

Conclusion

Today you learned a powerful and repeatable technique: converting a top-down, memoized DP solution into a bottom-up, tabulated one. This process not only removes the overhead of recursion but also paves the way for critical space optimizations.

Key Takeaways:

• Tabulation is an iterative approach that builds solutions from base cases upwards.
• You can convert a memoized solution to a tabulated one using a 5-step process:
  1. Define the DP state and create a corresponding array/table.
  2. Initialize the table with the problem's base cases.
  3. Determine the correct iteration order based on subproblem dependencies.
  4. Translate the recurrence relation into loop logic using table lookups.
  5. Identify the final answer in the completed table.
• Always look for space optimization opportunities. If a state dp[i] only depends on a constant number of previous states, you can likely reduce space complexity from O(n) to O(1).

You are now equipped with the two major approaches to implementing dynamic programming solutions. In our next lesson, we will put this knowledge into practice by solving classic 1D DP problems like Climbing Stairs and House Robber from scratch, solidifying the patterns you've learned today.