Dynamic Programming: Top-Down and Bottom-Up Approaches

Hello! Welcome to your next lesson in the "Advanced Algorithmic Patterns" module.

In the previous lesson, we established the two core properties that make a problem suitable for Dynamic Programming (DP): optimal substructure and overlapping subproblems. You learned to identify this "DP signature" by analyzing problems like Fibonacci and Climbing Stairs.

Today, we're moving from theory to practice. Our goal is to solve a classic 1D dynamic programming problem using both top-down memoization and bottom-up tabulation. You'll learn how to implement these two fundamental DP strategies, understand their trade-offs, and see how they transform an inefficient recursive solution into a highly performant one.

1. The Two Flavors of Dynamic Programming

Once you've identified a DP problem, you have two main approaches to solve it. Both aim to eliminate the redundant work caused by overlapping subproblems, but they do so in different ways.

Let's dive into the first approach: Memoization.

2. Top-Down DP: Memoization (Recursion + Caching)

Memoization is a top-down approach. You start by writing a standard recursive function that mirrors the problem's logic. Then, you augment it with a cache (often a hash map or an array) to store the results of subproblems.

Before computing a result, you check the cache.

• Cache Hit: If the result is already there, you return it immediately.
• Cache Miss: If not, you perform the computation, store the result in the cache, and then return it.

This pattern is likely familiar from your work on high-performance services. It's essentially function-level caching, where the function's arguments serve as the cache key. You prevent expensive re-computations, just as you'd cache the result of a costly database query or an API call.

Let's see this in action with a classic 1D DP problem.

The video clearly lays out the strategy. Now, let's apply it to a common interview problem: 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?

As we saw in the last lesson, the recurrence relation is ways(n) = ways(n-1) + ways(n-2).

Here's a Python implementation based on that pattern:

# LeetCode 70: Climbing Stairs (Top-Down with Memoization)

class Solution:
    def climbStairs(self, n: int) -> int:



        # The cache can be a dictionary or an array.
        # A dictionary is more flexible if the state isn't a simple integer index.
        memo = {}

        def dfs(i: int) -> int:



            # Base cases
            if i == n:
                return 1  # Found a valid path to the top
            if i > n:
                return 0  # Overshot the target




            # 1. Check the cache first (Cache Hit)
            if i in memo:
                return memo[i]




            # 2. Compute, store, and return (Cache Miss)
            # The number of ways from step 'i' is the sum of ways from the next two possible steps.
            memo[i] = dfs(i + 1) + dfs(i + 2)
            
            return memo[i]

        return dfs(0)


```grasp
{
  "type": "exercise",
  "id": "1a8b2d04-b803-48fe-b3a0-6e7a48d13709"
}

Example Usage:

solver = Solution()
print(f"Ways to climb 5 steps: {solver.climbStairs(5)}") # Output: 8

*   **Time Complexity:** $O(n)$. Each subproblem from `0` to `n` is computed exactly once.
*   **Space Complexity:** $O(n)$. This is due to the recursion depth, which can go up to `n`, and the size of the `memo` cache.

---




### 3. Bottom-Up DP: Tabulation (Iterative Table-Filling)

**Tabulation** is a bottom-up approach. Instead of starting from the top (`n`) and recursing down, you start from the smallest subproblems and iteratively build up the solution. You use an array, often called a DP table, to store the results.

The process is:
1.  Initialize a DP table of size `n+1`.
2.  Set the base cases in the table (e.g., `dp[0]`, `dp[1]`).
3.  Iterate through the table, using the recurrence relation to compute `dp[i]` based on previously computed values (e.g., `dp[i-1]`, `dp[i-2]`).
4.  The final answer is the value at `dp[n]`.

Let's continue with the Climbing Stairs example.

```grasp
{
  "type": "reading",
  "title": "70. Climbing Stairs - Solution & Explanation",
  "id": "[LINK](https://neetcode.io/solutions/climbing-stairs)",
  "url": "https://neetcode.io/solutions/climbing-stairs",
  "relevant_section_indices": [
    1
  ],
  "par_intro": "Now, let's look at the bottom-up approach for the same problem. The same NeetCode resource provides an excellent explanation and implementation.",
  "par_directions": "Read the section '3. Dynamic Programming (Bottom-Up)'. Focus on how the algorithm builds the solution iteratively from the base cases `dp[1]` and `dp[2]` upwards.",
  "estimated_time": "5 minutes"
}

Here is the corresponding tabulation implementation:

# LeetCode 70: Climbing Stairs (Bottom-Up with Tabulation)

class Solution:
    def climbStairs(self, n: int) -> int:
        if n <= 2:
            return n




        # 1. Initialize DP table
        # dp[i] will store the number of ways to reach step i
        dp = [0] * (n + 1)




        # 2. Set base cases
        dp[1] = 1  # 1 way to reach step 1 (1)
        dp[2] = 2  # 2 ways to reach step 2 (1+1, 2)




        # 3. Iterate and fill the table using the recurrence
        for i in range(3, n + 1):
            dp[i] = dp[i-1] + dp[i-2]




        # 4. The final answer is in dp[n]
        return dp[n]




# Example Usage:
solver = Solution()
print(f"Ways to climb 5 steps: {solver.climbStairs(5)}") # Output: 8

• Time Complexity: $O(n)$, as we iterate through the dp array once.
• Space Complexity: $O(n)$, for the dp array.

4. A More Involved Example: House Robber

Let's apply these patterns to a slightly more complex 1D problem: House Robber.

Problem: You are a professional 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 nums representing the money in each house, return the maximum amount you can rob.

At any house i, you have two choices:

1. Rob house i: You get nums[i] money, but you cannot rob house i-1. The total would be nums[i] + max_robbed_up_to(i-2).
2. Don't rob house i: You get no money from this house. The total would be max_robbed_up_to(i-1).

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

This problem perfectly illustrates how identifying the state and the choices at each step allows you to formulate a recurrence, which can then be implemented with either memoization or tabulation.

5. Trade-offs: Memoization vs. Tabulation

Choosing between the two approaches is a key engineering decision.

Here's a summary of the key trade-offs:

For you, an SDE II at AWS, this trade-off is critical. A stack overflow is an unrecoverable crash. For production systems where input size can be large, the iterative tabulation approach is often safer and more robust. However, during an interview, a memoized solution can sometimes be quicker to write and demonstrate your understanding of the core recursive structure.

Conclusion

You've now implemented your first 1D Dynamic Programming solutions. You've seen how a problem's recurrence relation is the key, and that it can be solved with two distinct but related strategies.

Key Takeaways:

• Memoization (Top-Down): Enhance a recursive function with a cache to avoid recomputing subproblems. It's often intuitive but carries the risk of stack overflow.
• Tabulation (Bottom-Up): Build an array (DP table) from the base cases up using an iterative loop. It's generally safer and slightly more performant for large inputs.
• Classic 1D DP problems like Climbing Stairs and House Robber are excellent for practicing these two fundamental patterns.
• The choice between them involves trade-offs in implementation complexity, performance, and memory safety.

Next Lesson Preview

In our next lesson, we will move into the next level of complexity: "Solve a classic 2D dynamic programming problem, analyzing the time and space complexity of the solution." We'll see how the principles of identifying a state, defining a recurrence, and applying memoization or tabulation extend naturally from a 1D array to a 2D grid.