How to Recognize Dynamic Programming Problems: Read the Signals Before You Code

You're three minutes into a problem. You know it's asking for a minimum. The constraint says n <= 1000. You're scribbling a greedy approach, something like "always pick the largest coin first," and it seems to work on the example. Nailed it, you think. You write the code. You submit.

It fails the second test case.

Five minutes gone. Not because you don't know dynamic programming. Because you didn't recognize a DP problem when it walked in wearing a greedy disguise.

DP recognition is a learnable skill. Problem statements are not random. They reuse the same language, the same constraint shapes, the same problem goals. Once you know what to look for, you can usually identify a DP problem before you've thought through a single recurrence.

"Minimum Number of" Is Almost Always DP

Problem statements telegraph the pattern through word choice. This is free information and most people ignore it.

These phrases reliably indicate DP:

• "minimum number of X to achieve Y" (coin change, jump game II)
• "maximum value you can collect" (knapsack, house robber)
• "number of distinct ways to reach" (climbing stairs, unique paths)
• "longest subsequence/substring satisfying" (LIS, LCS, palindromic subsequence)
• "can you partition / can you reach / is it possible" when brute force over subsets is implied

The constraint block reinforces the signal. n <= 1000 with an O(n²) time budget is a classic DP fingerprint. n <= 400 hints at O(n³) interval DP. n <= 20 with an exponential smell points toward bitmask DP.

The pattern isn't foolproof, but it gets you to the right neighborhood before you've written a single line.

Greedy Looks Right Until It Doesn't

Most DP problems look like greedy problems at first. This is the trap that destroys interview performance. You see "minimum number of coins," you think "always grab the largest coin," and the example works. You feel great. Then the hidden test case hits.

Coins {1, 3, 4}, target 6. Greedy grabs 4, leaving 2. Then 1 + 1. Three coins.

Optimal: 3 + 3. Two coins.

The greedy approach fails because picking the locally largest coin blocked a globally better combination. The current decision destroyed a future option that would have been better.

This is the structural test. Ask: can I construct a scenario where the locally optimal choice prevents the globally optimal outcome? For coin change with arbitrary denominations, yes. For activity selection (maximize count of non-overlapping intervals), no. Greedy works there because always picking the earliest-ending interval never blocks a better answer.

If you can build that counterexample, you need DP. The coin change case is one of five classic problems where the obvious first approach isn't optimal.

Every DP problem in disguise, looking very innocent until you see the constraints.

Define the State Before You Write Anything

This is where most DP solutions fall apart. The recurrence can be right but the state definition is fuzzy, and the code ends up subtly wrong in ways that are nearly impossible to debug under pressure. You'll get wrong answers that pass four test cases, then fail one, and you'll have no idea why.

The state is the minimum information needed to compute the answer for a subproblem without knowing how you got there.

For coin change: dp[i] = minimum coins to make amount i. The definition says nothing about which coins were chosen. You only need the amount. That's how you know the state is right. Given any i, you can compute dp[i] from smaller values without needing the history of choices.

For longest common subsequence: dp[i][j] = length of LCS considering the first i characters of string A and first j characters of string B. Two indices because you're consuming two sequences simultaneously.

State identification check: given the state, can you compute the answer purely from other states, with no external memory of past decisions? If you find yourself needing to remember "which path you took," you're missing a state variable.

Optimization Uses min/max. Counting Uses +.

DP splits into two structurally different families, and knowing which one you're in tells you the recurrence operator immediately.

Optimization problems ask for minimum or maximum. The recurrence selects:

# Coin change: minimum coins to make amount i
dp[i] = min(dp[i - coin] + 1 for coin in coins if coin <= i)

Counting problems ask how many ways. The recurrence sums:

# Climbing stairs: number of ways to reach step i
dp[i] = dp[i - 1] + dp[i - 2]

Same structure, different operator. The base case also flips: for optimization, the starting value is usually infinity or zero. For counting, it's 1 (one way to do nothing). Swap them and you get wrong answers that look completely plausible until some edge case exposes them.

Six Families Cover Most of What You'll See

Recognizing the family immediately tells you the state shape and the loop structure. This taxonomy sounds like a lot to memorize, but in practice three of these cover 80% of what shows up in interviews.

Linear (1D). State is a single index. Dependencies look backward one or two positions. House robber, climbing stairs, max subarray. Time O(n), space reducible to O(1).

Dual-sequence (2D). Two sequences processed together. State is two indices. LCS, edit distance, regex matching. Time O(mn), space reducible to O(min(m,n)) via rolling rows.

Knapsack. Items with weights and values, resource constraint. State is (item index, remaining capacity). 0/1 knapsack loops capacity backward to prevent item reuse. Unbounded loops forward. Partition equal subset sum, target sum, and coin change are all knapsack variants.

Interval (2D on range). State is dp[i][j] for the subarray from i to j. Iterate over increasing interval lengths. Burst balloons, matrix chain multiplication, palindrome partitioning II. Time O(n³), space O(n²).

State machine. The current state is an explicit dimension. Best time to buy and sell stock with cooldown has states: holding, not holding, in cooldown. Naming the states and transitions explicitly prevents invalid combinations and is the difference between getting the right answer and getting stuck for twenty minutes.

Bitmask. State encodes a subset of n items as bits. Useful when n <= 20 and you need to track which items have been visited. Traveling salesman (Held-Karp). Time O(2^n * n), space O(2^n).

When "First" Is Wrong, Think "Last"

Burst Balloons (LeetCode 312) is where candidates who genuinely understand DP still get stuck. It's not a knowledge problem. It's a framing problem.

You have balloons with values. Bursting balloon i gives you balloons[i-1] * balloons[i] * balloons[i+1] coins. Find the maximum total coins.

The naive attempt: for range [i, j], try each balloon as the one to burst first. The problem is that once you burst balloon k, its neighbors change. The subproblems interfere with each other and the recurrence falls apart.

The inversion: instead of which balloon to burst first, ask which balloon to burst last in range [i, j].

When balloon k is the last burst in [i, j], its neighbors at burst time are exactly balloons[i-1] and balloons[j+1]. They're guaranteed to still exist because k is declared the last one:

dp[i][j] = max(
    balloons[i-1] * balloons[k] * balloons[j+1] + dp[i][k-1] + dp[k+1][j]
    for k in range(i, j+1)
)

The subproblems dp[i][k-1] and dp[k+1][j] are fully independent now, because balloon k separates them and hasn't been burst when those ranges are solved.

This inversion appears across hard interval DP problems. Matrix chain multiplication asks which multiplication to perform last. Strange Printer (LC 664) asks which character to print last. When "first" creates dependent subproblems, try "last."

Five Steps for Every DP Problem

def solve_dp(nums: list[int]) -> int:
    n = len(nums)

    # 1. State definition: dp[i] = answer for subproblem at index i
    dp = [0] * (n + 1)

    # 2. Base case: answer for the empty subproblem
    dp[0] = 0

    # 3. Fill in order where dependencies (smaller indices) resolve first
    for i in range(1, n + 1):
        # 4. Transition: express dp[i] in terms of earlier states
        dp[i] = max(dp[i - 1], nums[i - 1] + dp[i - 2] if i >= 2 else nums[i - 1])

    # 5. Read the answer from the final state
    return dp[n]

State, base case, fill order, transition, answer location. If you can't clearly articulate each of these before writing a single line, stop. Fuzzy state definitions produce bugs that feel random but aren't. For the top-down memoized version, see memoization time complexity. For space-optimizing the table, see bottom-up DP.

SpaceComplexity covers DP recognition in voice-based mock interviews where you have to articulate the state aloud, which surfaces unclear thinking faster than any other method.

Three Traps That Kill Otherwise Correct Solutions

Wrong base case initialization. For optimization, dp[0] = 0 and all others = float('inf'). Reversing this makes the minimum look like infinity everywhere. You'll get an output, it just won't be correct. Trace dp[0], dp[1], dp[2] by hand before trusting the loop. This takes two minutes and saves ten.

Loop order in 2D DP. If dp[i][j] depends on dp[i-1][j] and dp[i][j-1], fill row-by-row, left-to-right. Draw the dependency arrows on your grid before writing the loops. Fill column-by-column and dp[i][j-1] is stale when you read it. The loop direction is not a stylistic choice.

Item reuse in knapsack. 0/1 knapsack (each item at most once): iterate capacity from high to low. Unbounded knapsack (item reuse allowed): iterate from low to high. The direction controls whether you see the current pass's updated value or the previous one. Swap the direction and items silently reuse or vanish. This mistake is silent and looks plausible, which is what makes it particularly brutal in an interview.

What Reading the Signals Actually Buys You

The first fifteen seconds after reading a problem are almost entirely pattern matching. You're not solving anything yet. You're filing the problem into a category so you can retrieve the right tools.

The signal words point to a family. The family points to a state shape. The state shape constrains the recurrence. The recurrence constrains the loop structure. Each step eliminates the majority of possible approaches and lets you start building something concrete.

Reading the signals correctly is not a shortcut around understanding DP. It's what understanding DP actually looks like.

Further Reading

• Dynamic Programming on Wikipedia
• Overlapping Subproblems Property on GeeksforGeeks
• Optimal Substructure Property on GeeksforGeeks
• Dynamic Programming Problems by Dimension on GeeksforGeeks
• LeetCode Coin Change Problem