Solving 1D DP: Memoization & Tabulation

In our last session, we developed the crucial skill of identifying Dynamic Programming problems by recognizing their two key ingredients: optimal substructure and overlapping subproblems. Now that you can spot a DP problem, it's time to learn how to solve it. This lesson will equip you with the two primary implementation strategies: the top-down approach with memoization and the bottom-up approach with tabulation.

Our focus will be on 1D Dynamic Programming problems, a fundamental category often encountered in technical interviews. By the end of this lesson, you'll be able to take a problem you've identified as suitable for DP and implement an efficient solution using either of these powerful techniques. We'll also cover the critical step of space optimization, a detail that separates good solutions from great ones in an interview setting.

1. The Two Faces of Dynamic Programming: Memoization and Tabulation

Once you've established the recurrence relation for a DP problem, you have two main ways to implement the solution.

Memoization (Top-Down): This approach is essentially "smart recursion." You write a standard recursive function but add a cache (like an array or a hash map) to store the results of subproblems. Before computing a result, you check the cache. If the answer is there, you return it instantly. If not, you compute it, store it in the cache, and then return it. This method often feels more intuitive because it follows the natural, problem-decomposing logic of recursion.
Tabulation (Bottom-Up): This is an iterative approach. Instead of starting from the top (the main problem), you start from the bottom (the smallest subproblems). You build a table (usually a 1D or 2D array) and fill it up from the base cases to the final solution. This approach avoids recursion and its associated call stack overhead, which can sometimes lead to better performance or prevent stack overflow errors for very deep recursion.

This image illustrates the conceptual difference between memoization (left), which follows a recursive, top-down tree-like path, and tabulation (right), which builds a solution iteratively from the ground up in an array.

For a direct comparison of their characteristics, the following resource provides an excellent summary.

Tabulation vs Memoization

This article from GeeksforGeeks provides a concise introduction to both techniques and a clear table comparing them side-by-side.

First, read the brief introductory paragraphs under the main heading to get the core definitions of Memoization and Tabulation. Then, focus on the comparison table, which contrasts the two methods on aspects like implementation difficulty and performance.

2. A Concrete Example: Solving Fibonacci

In the previous lesson, we used the Fibonacci sequence to illustrate the concept of overlapping subproblems, as shown in the recursive call tree below. Now, let's use it as our first practical example to implement both memoization and tabulation.

A recursive call tree for `fib(4)`, visually demonstrating the repeated computations of `fib(2)`, `fib(1)`, and `fib(0)` that we aim to eliminate.

The "take U forward" channel offers a masterclass on this exact progression, starting from the inefficient recursive solution and methodically optimizing it. We'll walk through its key segments.

DP 1. Introduction to Dynamic Programming | Memoization | Tabulation | Space Optimization Techniques

This video provides a step-by-step guide on solving the Fibonacci problem with DP, covering all the techniques we'll discuss.

The Problem: First, watch the section explaining the naive recursive approach from fibonacci number. This recaps the core issue of overlapping subproblems. Memoization (Top-Down): Next, see how to add a cache to the recursive solution in the segment from sub problem which has been solved. Pay close attention to the "three steps" he outlines: declaring the DP array, checking the cache before computing, and storing the result after computing. Tabulation (Bottom-Up): Now, observe how the solution is converted to an iterative, bottom-up approach from how do you convert. This eliminates recursion entirely. Space Optimization: Finally, and most importantly for interviews, watch the segment on space optimization from we are reducing or we are eliminating. This is a critical insight: since you only need the previous two values to calculate the next, you don't need to store the entire array.

To summarize the progression you just saw:

Naive Recursion: O(2^n) time, O(n) space (due to recursion depth). Inefficient.
Memoization (Top-Down): O(n) time, O(n) space (for cache) + O(n) space (for recursion stack). Much faster.
Tabulation (Bottom-Up): O(n) time, O(n) space (for DP table). No recursion overhead.
Space-Optimized Tabulation: O(n) time, O(1) space. The most optimal solution.

For a senior engineering role, interviewers expect you to arrive at the space-optimized solution. Being able to explain this entire progression demonstrates a deep understanding of the trade-offs.

3. A Classic Interview Problem: House Robber

Let's apply this framework to a common interview question, LeetCode 198: House Robber.

Problem: You are a robber planning to rob houses along a street. Each house has a certain amount of money. The only constraint is that you cannot rob adjacent houses. Given an array of integers nums representing the money in each house, return the maximum amount of money you can rob.

This is an optimization problem ("maximum amount"), a strong hint for DP. Let's figure out the recurrence relation. At any given house i, you have two choices:

Rob house i: You gain nums[i]. Since you can't rob the adjacent house i-1, the maximum you could have robbed before this house is the total from house i-2. Total: nums[i] + rob(i-2).
Do NOT rob house i: You gain nothing from this house. The maximum you could have robbed is simply the total from the previous house i-1. Total: rob(i-1).

The optimal solution for house i is the maximum of these two choices: rob(i) = max(nums[i] + rob(i-2), rob(i-1)). This is our recurrence relation.

The following video provides an excellent walkthrough of solving this problem from scratch, following the same optimization path as we did for Fibonacci.

House Robber - Leetcode 198 - Dynamic Programming (Python)

This video by Greg Hogg is a complete guide to solving the House Robber problem using every DP technique.

I recommend watching through the entire thought process, as it's a perfect model for an interview: bottom up dynamic programming: First, see the intuition behind the bottom-up DP table, which is often the easiest way to visualize the recurrence. the recursive solution: This section shows the naive top-down approach that will time out. top down DP or memorized solution: Here, he converts the naive recursion into an efficient memoized solution. bottom up firsts: This implements the bottom-up logic with a DP array (tabulation). bottomup constant space approach: Finally, this shows the space-optimized O(1) solution, which is the interview-grade answer.

Notice the identical optimization pattern: just like with Fibonacci, the solution for dp[i] only depends on dp[i-1] and dp[i-2]. This allows you to discard the full DP array and use only two variables to track the previous two maximums, reducing space complexity from O(n) to O(1).

4. Another 1D DP Pattern: The Rod Cutting Problem

Let's look at one more 1D DP problem that has a slightly different structure: the Rod Cutting problem.

Problem: You are given a rod of length n and an array of prices where price[i] is the price of a rod piece of length i+1. Determine the maximum value obtainable by cutting up the rod and selling the pieces.

For a rod of length i, you can make a cut of length j (where 1 <= j <= i). The profit would be price[j-1] plus the maximum profit you can get from the remaining rod of length i-j. You must try all possible first cuts j and take the maximum.

The recurrence relation looks like this: maxValue(i) = max(price[j-1] + maxValue(i-j)) for all j from 1 to i.

The GeeksforGeeks article we referenced earlier uses this exact problem to demonstrate memoization and tabulation. Since you're proficient in JavaScript, the code examples will be directly applicable.

Tabulation vs Memoization

This article provides a clear definition and full code implementations for solving the Rod Cutting problem with both DP approaches.

Start by reading the problem description. Next, study the Memoization approach. Read the explanation under Using Top-Down DP and then analyze the JavaScript code block. Notice how it's a recursive function with a memo array. Finally, examine the Tabulation approach. Read the explanation under Using Bottom-Up DP and review its corresponding JavaScript code. Observe the nested loops that build the dp table from the smallest rod lengths up.

Unlike Fibonacci and House Robber, the space optimization for this problem isn't as straightforward to O(1) because maxValue(i) depends on potentially all smaller subproblems, not just one or two immediate predecessors. This highlights that while space optimization should always be considered, its feasibility depends on the specific recurrence relation.

Conclusion

In this lesson, we moved from theory to practice, implementing solutions for 1D Dynamic Programming problems. You've learned the two fundamental techniques—memoization and tabulation—and seen how to apply them to classic problems. Most importantly, you've learned the critical interview skill of optimizing a DP solution's space complexity when the recurrence allows for it.

Key Takeaways:

Memoization (Top-Down) is recursion with caching. It's often a more direct translation of a recursive thought process.
Tabulation (Bottom-Up) is iteration with a table. It avoids recursion overhead and can be more intuitive for problems where the state transitions are linear.
The general workflow is: Identify Recurrence -> Implement (Memoization or Tabulation) -> Optimize Space.
For problems like Fibonacci or House Robber, where dp[i] depends only on a constant number of previous states (e.g., dp[i-1], dp[i-2]), you can optimize space from O(n) to O(1). This is a crucial optimization to discuss in an interview.

In our next lesson, we will build upon the tabular thinking developed here and extend it into another dimension. We will tackle 2D Dynamic Programming problems, such as finding the Longest Common Subsequence, which are common in bioinformatics, version control systems, and, of course, technical interviews.