Dynamic Programming Is Just Recursion With a Memory. Here's the Framework.

You open a LeetCode problem. It says "find the minimum cost." You read it twice. Then a third time. You recognize it smells like dynamic programming. And then nothing. You stare at the cursor blinking in an empty function body, waiting for inspiration that apparently took a wrong turn somewhere around your third Fibonacci walkthrough.

This happens to almost everyone. Not because DP is some arcane art reserved for ex-Googlers with floor-to-ceiling whiteboards. Because nobody teaches the process, just the solutions. You watch someone code up a clean DP table and think "obviously," but when you sit down alone, the blank state definition mocks you.

DP is one of the most learnable topics in DSA, precisely because all dynamic programming problems follow the same skeleton. Once you see it, you can't unsee it.

Why Everyone Freezes at DP

Richard Bellman coined "dynamic programming" in the 1950s and later admitted the name was pure marketing. "Dynamic" sounded impressive to military funders. "Programming" meant optimization, not code. A more honest name might have been "caching recursive decisions," but that has approximately zero grant money energy. The vague branding stuck, and so did the mystique.

Most DP tutorials make it worse by jumping straight to the table: here are the rows, here are the columns, here is the recurrence. They skip the ten-minute thinking phase that makes all of that obvious. It's like teaching someone to drive by handing them the keys to a manual on a hill.

DP is not a data structure technique. It is a proof technique. You are proving, by induction, that you can build the answer to a big problem from answers to smaller problems you have already solved. Once you internalize that, the rest is bookkeeping.

Two Signals That Tell You DP Applies

Before you define a single dp array, confirm the problem is actually DP. Two signals.

Overlapping subproblems. When brute force recursion solves the same sub-case more than once, that is redundancy you can eliminate by caching. Computing fib(40) naively generates roughly 2^40 calls. Over a trillion. Memoization cuts it to 40. Same answer, completely different universe of speed.

Optimal substructure. The best solution to the whole problem is built from best solutions to its parts. Shortest path has this. If you can discard all but the best sub-solutions and still reach a globally optimal answer, you have it.

You will see both signals in every classic: climbing stairs, coin change, 0/1 knapsack, longest common subsequence, longest increasing subsequence. Confirm both before designing anything.

Write the Brute Force. Watch It Break.

The wrong approach most people try: stare at the problem until the DP table materializes in your brain. This works if you have solved hundreds of problems. For everyone else, it is a great way to spend 45 minutes producing a blank screen and a mild existential crisis.

The right approach: write the recursive brute force first, then look at the call tree.

Take coin change. Given coins [1, 5, 10] and target 11, find the minimum coins needed.

def coin_change(coins: list[int], amount: int) -> int:
    if amount == 0:
        return 0
    if amount < 0:
        return float('inf')

    best = float('inf')
    for coin in coins:
        result = coin_change(coins, amount - coin)
        best = min(best, result + 1)
    return best

This works. It is also catastrophically slow. For amount = 11, the recursion fans out into a tree where coin_change(5) gets called from multiple branches. Draw the call tree and you will see the same nodes repeating. That repetition is the overlapping subproblems signal. You just found it by watching the brute force embarrass itself.

Your brute force solution on small inputs vs. your brute force solution on large inputs.

Get the State Wrong and Nothing Else Matters

This is where most candidates crater. Your state must contain exactly the information needed to compute any subproblem without any external context. Most tutorials skip this, which explains why DP feels like guessing and not engineering.

For coin change, the only changing variable is amount. So dp[i] = minimum coins to make amount i. Information-sufficient. Given dp[i], you do not need to know how you got there or which coins came before.

Now compare to longest increasing subsequence (LIS). A common wrong state: dp[i] = length of LIS in nums[0..i]. The problem is this definition blocks the transition. To extend an LIS, you need to know whether the current element is greater than the last element of the subsequence. "In 0..i" does not tell you that.

The correct state: dp[i] = length of LIS ending at index i.

def length_of_lis(nums: list[int]) -> int:
    dp = [1] * len(nums)

    for i in range(1, len(nums)):
        for j in range(i):
            if nums[j] < nums[i]:
                dp[i] = max(dp[i], dp[j] + 1)

    return max(dp)

Now the transition is clear: for each j < i, if nums[j] < nums[i], then dp[i] = max(dp[i], dp[j] + 1). The "ending at" anchor gives you exactly what you need to compare.

If you cannot write the transition, your state definition is missing information. Add a second index, change the anchor point, or find the variable that makes the transition possible. The transition not working is the diagnostic, not an excuse to guess randomly.

Memoize First, Then Optimize If You Must

Once you have a recursive solution you understand, memoization is mechanical. Cache the result before returning. Three lines change, nothing else does.

from functools import lru_cache

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

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

This already runs in O(amount * len(coins)). For most interviews, stop here.

The @lru_cache decorator, sitting there, doing nothing, waiting for you to use it.

Tabulation converts this to an iterative table. You compute every subproblem in an order such that when you need dp[i - coin], it is already filled.

def coin_change(coins: list[int], amount: int) -> int:
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0

    for i in range(1, amount + 1):
        for coin in coins:
            if coin <= i:
                dp[i] = min(dp[i], dp[i - coin] + 1)

    return dp[amount] if dp[amount] != float('inf') else -1

Tabulation eliminates recursion stack overhead and any risk of stack overflow on large inputs. The trade-off: you have to figure out the correct iteration order yourself, which is not always obvious with 2D problems.

Use memoization to understand the problem, then translate to tabulation if you need space optimization or production-grade performance.

Four Steps for Solving Dynamic Programming Problems

After enough problems, the same four steps emerge every time.

1. Spot the signals. Does brute force re-solve the same subproblem? Can sub-solutions compose into the final answer? Both yes means DP applies.

2. Define the state. What is the minimum information needed to fully specify a subproblem? Start 1D. Move to 2D only when the 1D state cannot support the transition.

3. Write the recurrence. Given all smaller states, how do you compute the current one? Write this as a formula before any code. dp[i] = min(dp[i - coin] + 1 for coin in coins) is a recurrence. The code follows from it.

4. Handle base cases. Find the trivially answerable subproblems: empty string, zero amount, a single element. Initialize those before the loop, or they will silently corrupt every state that depends on them.

This skeleton does not change whether you are doing climbing stairs or edit distance. The problem changes. The process does not.

If you practice DP problems in mock interviews, this framework is also how you narrate to the interviewer. They are not only grading your code. They are watching whether you can decompose a problem systematically and explain it out loud. SpaceComplexity runs timed mock DSA interviews with rubric-based feedback specifically on this kind of structured reasoning, so you can drill the verbal explanation before a real interview makes you freeze.

The Space Optimization Worth Mentioning

Once you have a tabulation solution, you often have a free space optimization waiting. If your recurrence only reads the previous row of a 2D table, you do not need the full table.

LCS naive tabulation uses O(m * n) space. But the transition only reads the current and previous rows. You can compress to two 1D arrays.

def lcs(text1: str, text2: str) -> int:
    prev = [0] * (len(text2) + 1)

    for char1 in text1:
        curr = [0] * (len(text2) + 1)
        for j, char2 in enumerate(text2):
            if char1 == char2:
                curr[j + 1] = prev[j] + 1
            else:
                curr[j + 1] = max(prev[j + 1], curr[j])
        prev = curr

    return prev[len(text2)]

This is called the rolling array technique. Space drops from O(m * n) to O(n). You do not need this to pass most interviews. But mentioning it signals that you understand the memory layout of your DP, not just the algorithm. That distinction is what separates a "pass" from a "strong hire."

The Short Version

• DP is proof by induction. Build big answers from small answers you have already locked in.
• Two signals before committing: overlapping subproblems and optimal substructure.
• Write the brute force recursion first. The call tree shows where subproblems repeat.
• State definition is the hardest part. Your state must be information-sufficient: the transition has to follow from it with no external context.
• If you cannot write the transition, your state is missing something. Add a dimension or change the anchor.
• Memoize top-down to understand. Tabulate bottom-up to optimize.
• Rolling arrays compress 2D tables to 1D when your recurrence only reads the previous row.

Grinding LeetCode solutions without building this mental model is a trap. If that sounds familiar, You're Practicing LeetCode Wrong is worth reading next. And when you are ready to practice the live explanation under time pressure, try SpaceComplexity.

Further reading

• Dynamic programming (GeeksforGeeks) — worked examples across the classic problem types.
• Knapsack problem (Wikipedia) — the canonical optimal-substructure problem.
• Longest common subsequence (Wikipedia) — the 2D table and rolling-array optimization in depth.