Recursion to Memoization

Recursion to Memoization - aloalgo.com

Dynamic Programming (DP) is one of those topics that feels foggy… until it suddenly snaps into focus. This chapter covers the foundation: what DP is and how to use memoization to optimize recursive solutions.

Dynamic Programming is an optimization technique used to solve problems that exhibit two key properties:

Overlapping subproblems - the same smaller problems are solved repeatedly.
Optimal substructure - the optimal solution to a problem can be built from optimal solutions to its subproblems.

Instead of recomputing the same answers again and again, DP stores results and reuses them. The result is often a dramatic reduction in time complexity.Classic signals that DP might apply:

"Find the number of ways…"
"Maximize / minimize…"
"Given constraints, what is the optimal…"

Let's look at a classic example: computing the nth Fibonacci number.

The problem? We're computing the same values over and over. The time complexity is O(2^n) - exponential! For fib(50), this would take billions of operations.

Memoization means caching the results of function calls so that repeated calls with the same arguments return the cached result instead of recomputing.

With one line (@lru_cache(None)), we transformed an O(2^n) solution into O(n). That's the power of memoization.

You can also implement memoization manually with a dictionary:

A simple mental checklist for DP problems:

F – Define the Function
What does dp(state) represent?

A – Arguments (State)
What variables uniquely define a subproblem?

S – State Transition
How do you move from one state to smaller states?

T – Termination
What are the base cases?

If you can answer these four questions, you can write a DP solution.

Problem: You can climb 1 or 2 stairs at a time. How many distinct ways can you climb n stairs?

F - Function: climb(n) = number of ways to reach stair n
A - Arguments: n (current stair)
S - Transition: climb(n) = climb(n-1) + climb(n-2)
T - Termination: climb(0) = 1, climb(1) = 1

Start with brute force recursion, then optimize with memoization
Draw small examples by hand to understand the pattern
Clearly define what your DP function returns
In Python, @lru_cache(None) is your best friend for interviews
Always ask: What are the overlapping subproblems?

Pros	Cons
- Easier to reason about - Natural fit for recursive thinking - Faster to write in interviews - Only computes needed states	- Risk of recursion depth limits - Slight overhead from function calls - May use more memory than tabulation

Interview recommendation: Memoization is usually easier, faster, and safer under time pressure. Start here unless you have a specific reason to use tabulation.

Now that you understand memoization, continue to 1D Dynamic Programming to learn about tabulation and see more examples.

Was this helpful?

Study plan All problems

Cheat Sheet

Recursion to Memoization

What is Dynamic Programming?

The Problem with Plain Recursion

Memoization: The Fix

Manual Memoization

The FAST Strategy

Example: Climbing Stairs

Tips for Success

When to Use Memoization

Practice Problems

Next Steps

Company

Practice

Learn