Dynamic Programming Memoization: DP Is Brute-Force Recursion You Stopped Repeating

Dynamic programming is not a separate algorithm. It's brute-force recursion where you noticed you were repeating yourself and added memoization.

Write the brute force. Find the repeated work. Name what makes each call unique. Add a cache. That's DP. Nobody is born knowing this, and most tutorials make it worse before they make it better.

Why the Jargon Gets in the Way

"Overlapping subproblems." "Optimal substructure." "Bottom-up tabulation." These terms are real, but teaching them before the basic idea lands is backwards. It's like explaining the punchline instead of telling the joke.

The jargon describes a pattern you can see. It does not teach you to see it.

Most people freeze on DP problems because they try to design the solution from scratch: figure out the state space, sketch the recurrence, fill in the table. That sequence starts with the hardest step.

The reason DP is feared isn't the algorithm. It's the teaching order. You can't see the pattern until you've written the recursion. You can't write the recursion until you understand the problem. But most tutorials open with the optimized table solution and then tell you to reverse-engineer why it works. That's not how brains learn things.

Start with brute force instead.

Every DP tutorial, approximately 90 seconds in

The Fibonacci Trap

Everyone teaches DP on Fibonacci. It's the Hello World of DP explanations, which makes it also the Hello World of "I understood this example and still cannot solve Coin Change."

def fib(n):
    if n <= 1:
        return n
    return fib(n - 1) + fib(n - 2)

This is exponential. fib(5) calls fib(3) twice. fib(10) calls fib(5) eight times. Draw the call tree and the same subtrees appear everywhere. The function recomputes results it already has, like doing long division on the same pair of numbers repeatedly and then starting over from scratch.

fib(3) gets called from fib(5) directly and from fib(4). Neither call checks if the other already did the work.

The fix is one decorator:

from functools import lru_cache

@lru_cache(maxsize=None)
def fib(n):
    if n <= 1:
        return n
    return fib(n - 1) + fib(n - 2)

O(2^n) becomes O(n). That's memoization, and memoization is DP.

But Fibonacci doesn't teach the real skill. The state is obvious. One parameter. Of course you cache on n. There's nothing else it could possibly be. The reason DP problems feel hard in interviews is everything after Fibonacci, where the state is not obvious and figuring out the minimum set of parameters that uniquely identifies a call is actually the work.

Naming the State Is the Whole Game

The real work in DP is one question: what is the minimum information a recursive call needs?

That's naming the state. Once you can name it, the recursion almost writes itself. The cache is just a dictionary.

Coin Change: given coins like [1, 5, 10, 25] and a target amount, find the minimum number of coins. Most people freeze here. Not because the problem is impossible, but because they're trying to picture the DP table before they understand the recursion that fills it.

Ignore optimization entirely and write the brute force. What does a recursive call need to know? Just the remaining amount. That's the state.

def coin_change(coins: list[int], amount: int) -> int:
    def solve(remaining: int) -> int:
        if remaining == 0:
            return 0
        if remaining < 0:
            return float('inf')
        return min(1 + solve(remaining - c) for c in coins)

    result = solve(amount)
    return result if result != float('inf') else -1

This is correct and exponential. Test it on small inputs. Now look for repeated work: solve(11) with [1, 5] will compute solve(6) from multiple branches. Same state, recomputed from scratch every time.

Add the cache:

from functools import lru_cache

def coin_change(coins: list[int], amount: int) -> int:
    @lru_cache(maxsize=None)
    def solve(remaining: int) -> int:
        if remaining == 0:
            return 0
        if remaining < 0:
            return float('inf')
        return min(1 + solve(remaining - c) for c in coins)

    result = solve(amount)
    return result if result != float('inf') else -1

O(amount × len(coins)). The complexity fell out of the structure. You didn't have to derive it separately. You named the state, added four lines, and now you're doing DP. That's the whole trick.

You, about twenty minutes from now

When the State Needs Two Dimensions

The intuition scales. The state just gets bigger.

Longest Common Subsequence: a recursive call needs its position in each string. State is (i, j). Two parameters instead of one. Same idea.

from functools import lru_cache

def lcs(s1: str, s2: str) -> int:
    @lru_cache(maxsize=None)
    def solve(i: int, j: int) -> int:
        if i == len(s1) or j == len(s2):
            return 0
        if s1[i] == s2[j]:
            return 1 + solve(i + 1, j + 1)
        return max(solve(i + 1, j), solve(i, j + 1))

    return solve(0, 0)

State space is m × n. O(mn) time, O(mn) cache. Every hard DP problem follows this same shape.

Ask what the subproblem needs. Write the recursion. Add the cache. The question is the skill, not the table.

Stop Designing DP. Start Writing Brute Force.

DP problems look impossible when you approach them as "find the DP solution." That's backwards.

The sequence that works:

1. Write the brute-force recursion. Get it correct on small inputs first.
2. Draw a few branches of the call tree. Find the repeated subproblems.
3. Name the state: what parameters uniquely identify a call?
4. Add @lru_cache. That's your memoized solution.

If you want the bottom-up version, it's a mechanical translation: fill a table in the same order recursion would evaluate the calls. The framework for that translation is worth learning once top-down feels automatic.

The brute-force recursion is already 90% of the answer. The cache is the last 10%, and once you can name the state, adding it is mechanical. The fear around DP is mostly a teaching artifact. The algorithm itself is just recursion with a good memory.

If you want to practice this live, with follow-up questions and scored feedback on your reasoning, SpaceComplexity runs rubric-based DSA mock interviews on demand.