Dynamic Programming: Recurrence Relations and Memoization

In our previous lesson, we established the conceptual foundation for Dynamic Programming by learning to identify problems with optimal substructure and overlapping subproblems. We saw how a naive recursive approach to problems like calculating Fibonacci numbers leads to an exponential number of redundant calculations.

Today, we will take the next logical step: turning that conceptual understanding into a practical, efficient coding pattern. You will learn how to formulate a recurrence relation for a given problem and then implement a top-down DP solution using memoization. This technique directly tackles the issue of overlapping subproblems and is one of the most intuitive ways to write a DP solution, especially during a coding interview. We'll start with the familiar Fibonacci sequence and then apply the same pattern to another classic problem, Climbing Stairs.

From Recurrence to Recursion to Memoization

The journey to a top-down DP solution follows a clear, three-step path. This pattern is fundamental and, once mastered, can be applied to a wide range of problems.

1. Formulate the Recurrence Relation: Based on the problem's optimal substructure, define the solution to a larger problem in terms of the solutions to its smaller subproblems.
2. Write the Brute-Force Recursive Solution: Directly translate the recurrence relation into a recursive function. This solution will be correct but inefficient.
3. Add Memoization: Introduce a cache (an array or a hash map) to store the results of subproblems. This avoids re-computation and transforms the exponential solution into a polynomial one.

Let's walk through this process with the Fibonacci sequence.

The Fibonacci Example Revisited

In the last lesson, we identified the recurrence for Fibonacci numbers as $F(n)=F(n-1)+F(n-2)$, with base cases $F(0)=0$ and $F(1)=1$. A direct recursive translation leads to the massive tree of overlapping computations we saw previously.

Now, let's see how to fix this inefficiency. The core idea of memoization is simple: if you've already solved a subproblem, just look up the answer instead of solving it again.

The following video provides an excellent, structured walkthrough of how to convert a plain recursive solution into a memoized one. It introduces a clear, step-by-step method that you can use as a template for many DP problems.

The article below provides a detailed implementation of this exact logic in Python. It walks through the naive approach, analyzes its inefficiency, and then presents the optimized code using memoization.

With memoization, the recursion tree is effectively "pruned." Once a subproblem like fib(2) is computed, any subsequent call to it immediately returns the stored value, cutting off that entire branch of the recursion tree.

Applying the Pattern: The Climbing Stairs Problem

Now let's apply this exact pattern to a new problem that, on the surface, might not look like Fibonacci. This is where your pattern recognition skills, honed from solving LeetCode problems, come into play.

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?

Step 1: Formulate the Recurrence

Let's define ways(n) as the number of distinct ways to climb a staircase of n steps.
To reach the n-th step, what was your final move?

• You could have taken a single step from step n-1.
• Or, you could have taken two steps from step n-2.

The total number of ways to reach step n is the sum of the ways to reach step n-1 and the ways to reach step n-2. This gives us a recurrence relation:
$\text{ways}(n)=\text{ways}(n-1)+\text{ways}(n-2)$
This is exactly the same recurrence structure as the Fibonacci sequence! The only difference is the base cases.

• ways(1): 1 way (a single 1-step climb).
• ways(2): 2 ways (1-step + 1-step, or a single 2-step climb).

Steps 2 & 3: Implement with Memoization

Now that we have the recurrence, we can directly implement a memoized solution. The following resource provides a clear walkthrough, starting from the brute-force recursion and evolving it to the optimized top-down DP solution.

To get another perspective, the following video provides a fantastic visualization of the recursion tree for the Climbing Stairs problem and how memoization dramatically prunes it.

Conclusion

In this lesson, you translated the theoretical properties of DP into a concrete implementation strategy. The top-down approach with memoization is a powerful and intuitive pattern: it preserves the natural, problem-solving structure of recursion while eliminating its primary inefficiency.

Key Takeaways:

• Top-Down DP Pattern:
  1. Define a recurrence relation based on optimal substructure.
  2. Implement it as a plain recursive function.
  3. Augment the function with a cache (memo) to store and retrieve subproblem results, avoiding re-computation.
• The Memoization Logic: The pattern involves two key additions to a recursive function:
  1. Check the cache: At the start of the function, check if the solution for the current state is already computed. If so, return it.
  2. Save to cache: Before returning a newly computed result, store it in the cache.
• Pattern Recognition: Problems like Climbing Stairs can be revealed to be structurally identical to Fibonacci once you derive their recurrence relation. Recognizing these underlying patterns is a key skill.

In our next lesson, we'll explore the second major DP implementation technique: bottom-up dynamic programming, also known as tabulation. It solves the same problems but uses an iterative approach, building solutions from the smallest subproblems upwards.