From Memoization to Tabulation: The Fibonacci Example

1. Recap: Memoization (Top-Down)

Let's quickly recall our memoized solution for the N-th Fibonacci number.

// Helper function with memoization
private int fib(int n, int[] memo) {
    // Base cases
    if (n <= 1) {
        return n;
    }
    // 1. Check if the result is already computed
    if (memo[n] != -1) {
        return memo[n];
    }
    // 2. Compute and store the result before returning
    memo[n] = fib(n - 1, memo) + fib(n - 2, memo);
    return memo[n];
}

// Main function to initiate the process
public int fibonacci(int n) {
    // 3. Create and initialize the storage
    int[] memo = new int[n + 1];
    Arrays.fill(memo, -1);
    return fib(n, memo);
}

This approach starts from the top (n) and breaks the problem down, solving subproblems as needed. It's intuitive because it closely follows the mathematical recurrence. However, the reliance on recursion can lead to StackOverflowError for very large n and carries some function call overhead.

2. Tabulation: The Bottom-Up Approach

Tabulation takes the opposite approach. Instead of starting from n and going down, it starts from the smallest subproblems and builds its way up to the final solution.

• Top-Down (Memoization): Starts at fib(n) and recursively calls fib(n-1), fib(n-2), etc., until it hits base cases.
• Bottom-Up (Tabulation): Starts by solving fib(0) and fib(1), then uses those results to solve fib(2), then uses that to solve fib(3), and so on, until it reaches fib(n).

This iterative method "fills a table" of results from the bottom up, hence the name "tabulation."

3. Converting Fibonacci from Memoization to Tabulation

The conversion process is systematic and follows a clear logic. We'll use the same recurrence relation, F(n) = F(n-1) + F(n-2), but apply it iteratively.

Let's break this down into a step-by-step process for implementation in Java.

Step 1: Create the DP Table
Create an array, let's call it dp, of size n + 1 to store the Fibonacci numbers up to n.
int[] dp = new int[n + 1];

Step 2: Initialize the Base Cases
This is the "bottom-up" part. We start by filling in the answers we already know. For Fibonacci, the base cases are F(0) = 0 and F(1) = 1.
dp[0] = 0;
dp[1] = 1;

Step 3: Iterate and Fill the Table
Write a loop that iterates from i = 2 up to n. In each step, calculate dp[i] using the results of the previous subproblems, which are already stored in the table.
for (int i = 2; i <= n; i++) { dp[i] = dp[i-1] + dp[i-2]; }

Step 4: Return the Final Answer
The answer to our original problem, fib(n), is now stored at the last computed index of our table.
return dp[n];

Here is a visual representation of the table being filled for n=6:

Here is the complete Java code for the tabulated solution.

4. Memoization vs. Tabulation

You now know both major DP techniques. Let's summarize their key differences. This is a very common discussion point in interviews.

5. Space Optimization: A Common Follow-up

For the Fibonacci problem, if you look at the tabulated recurrence dp[i] = dp[i-1] + dp[i-2], you'll notice that to compute the current value dp[i], we only need the two previous values. We don't actually need the entire dp array of size n+1.

This observation allows for a significant optimization, which is a frequent follow-up question in interviews. We can reduce the space complexity from O(n) to O(1).

Instead of an array, we can use just two variables to keep track of the previous two Fibonacci numbers.

Here's the space-optimized Java code:

public int fibonacci(int n) {
    if (n <= 1) {
        return n;
    }

    int prev2 = 0; // Represents fib(i-2)
    int prev1 = 1; // Represents fib(i-1)

    for (int i = 2; i <= n; i++) {
        int current = prev1 + prev2;
        prev2 = prev1;
        prev1 = current;
    }

    return prev1; // prev1 holds the final fib(n)
}

This is the most efficient way to solve the Fibonacci problem, with O(n) time complexity and O(1) space complexity.

Conclusion

Excellent work! You've now mastered the two fundamental approaches to dynamic programming: top-down with memoization and bottom-up with tabulation. Understanding when and how to apply each is crucial for tackling a wide range of algorithmic problems.

Key Takeaways:

• Tabulation is a bottom-up, iterative approach to DP that builds solutions from base cases.
• It avoids recursion, which can prevent stack overflow errors and reduce overhead.
• The conversion process involves: creating a DP table, initializing base cases, and iterating to fill the table using the recurrence relation.
• For some problems like Fibonacci, the tabulated solution can be space-optimized if the current state only depends on a fixed number of previous states.

Preview of the Next Lesson:
We've used the Fibonacci sequence as a learning tool because its state is defined by a single variable (n), leading to a 1D DP array. In our next lesson, we'll level up by tackling the classic 0/1 Knapsack problem. This will require us to manage a state defined by two variables, introducing us to the world of 2D dynamic programming.