How to Spot a Dynamic Programming Problem in Interviews

Learning how to spot a dynamic programming problem starts with one question: can you describe repeated work as a reusable state? If several decision paths reach the same subproblem, you can solve that state once and reuse its result.

That observation matters more than memorizing a list of dynamic programming patterns. It gives you a repeatable path from brute force to a recurrence, then to code you can explain in an interview.

What Makes a Problem Dynamic Programming?#

A problem fits dynamic programming when its solution can be built from reusable subproblem results.

Two properties usually make that possible:

• Overlapping subproblems: different decision paths ask you to solve the same state.
• Optimal substructure: the answer for a larger state can be assembled from correct answers to smaller states.

These phrases become useful only when you attach them to a concrete state.

Suppose a recursive search reaches the question, “What is the best result starting at index i?” If several earlier choices can lead to that exact question, the recursion repeats work. Cache the answer for i, and the repeated branch becomes a lookup.

Optimal substructure means your recurrence can trust smaller answers. If the best answer at i depends on the best answers at i + 1 and i + 2, you do not need to preserve every path used to produce those answers. You need only their results.

Dynamic programming is not limited to optimization. A state might return:

• A maximum or minimum value.
• The number of valid constructions.
• Whether a target is reachable.
• The length of a sequence.
• The cost of transforming one prefix into another.

The result must also contain enough information for its caller. A recurrence that discards information needed by future choices does not have valid optimal substructure.

Recognizing DP is separate from choosing memoization vs tabulation. Memoization evaluates states through recursive calls and caches them. Tabulation evaluates states in an explicit order. Both can implement the same DP state and recurrence.

You can explore common state shapes in the dynamic programming pattern hub.

The Clues That Suggest Dynamic Programming#

Dynamic programming interview questions often combine a repeated choice with a finite state that summarizes everything relevant so far.

The result has a DP-shaped form#

Pay attention when the problem asks for:

• The maximum profit, score, or length.
• The minimum cost, number of operations, or number of items.
• The number of ways to construct or reach something.
• Whether a target is possible.
• The best result under a capacity or adjacency restriction.

These outputs are clues, not proof. A maximum might have a greedy solution. Feasibility might reduce to graph reachability. Counting might have a direct mathematical formula.

The same choice repeats#

Look for decisions that recur across a structured input:

• At each position, take an item or skip it.
• At each capacity, use an item or leave it.
• For each interval, choose a split point.
• For each subset, add another element.
• At each pair of string indices, match, insert, delete, or replace.
• At each grid cell, move through an allowed neighbor.

A repeated choice gives you the outline of a brute-force decision tree. The state describes where you are in that tree.

The decision tree merges#

Imagine writing the direct recursive solution. Do separate branches eventually call the function with identical arguments?

Consider a function solve(i) that can move to solve(i + 1) or solve(i + 2). One branch reaches solve(i + 2) directly. Another reaches solve(i + 1) and then advances once. That merged call is evidence of overlapping subproblems.

This is the strongest practical clue for how to identify dynamic programming. Draw the first few levels of recursion. Mark repeated function arguments. If you can cache those arguments without changing the meaning of the answer, DP is plausible.

The constraints support the hypothesis#

Constraints help you reject impossible approaches. They do not establish the correct pattern by themselves.

An input too large for exhaustive subset generation suggests that exponential search will fail. A bounded capacity may permit a table indexed by capacity. Small subset sizes may make a bitmask state practical.

Still, derive the state before choosing DP. Constraints tell you what might fit. The recurrence tells you whether it is correct.

A Decision Checklist for Testing the Pattern#

You can validate a suspected DP problem by defining the decision, state, recurrence, and base cases before writing implementation code.

State the decision#

Complete this sentence:

At this state, I choose between ___ and ___.

Examples include taking or skipping an item, matching or not matching two characters, and placing or not placing a value.

If you cannot name the choice, you may not yet understand the brute-force structure.

Find the smallest complete state#

Ask what information uniquely determines all remaining choices and their outcomes.

A state might be:

• dp(i): the best answer starting at index i.
• dp(i, remaining): the answer from index i with some capacity left.
• dp(left, right): the answer for one interval.
• dp(row, col): the answer from one grid position.
• dp(mask, last): the answer after selecting a subset and ending at one element.

Do not record history merely because it happened. Record it only when it changes what can happen next.

Check whether paths merge#

Take two different partial decision paths. If they reach the same state variables, ask whether their future possibilities are identical.

If yes, they are the same subproblem. Reuse one result.

If their future possibilities differ, your state is missing information. Add only the dimension that explains the difference.

Write the recurrence#

Write the mathematical or pseudocode relationship before code. For a take-or-skip problem, it might be:

dp(i) = max(
    value[i] + dp(next index after taking),
    dp(next index after skipping)
)

Name what every branch means. This catches invalid transitions earlier than debugging an array.

Establish the base cases#

State what happens when no decisions remain. Then verify that each transition moves closer to that condition.

For an index moving right, a common base case is dp(i) = 0 when i has passed the input. For a remaining capacity, the base may apply when the capacity is zero. Interval DP usually moves toward shorter intervals.

A recurrence without progress can loop. A table filled in the wrong direction can read states that do not exist yet.

Dynamic Programming Versus Similar Patterns#

DP is appropriate when reusable state results matter; similar patterns differ in what they reuse or enumerate.

DP versus greedy#

Both patterns often appear in optimization problems. A greedy algorithm makes one locally attractive choice and does not reconsider it. DP preserves the results of multiple choices until it can compare them.

Do not choose greedy because “taking the largest value seems right.” Give an exchange argument or another proof that an optimal solution can include the greedy choice. If you cannot, define the competing choices and test a DP recurrence.

DP versus backtracking#

Backtracking is appropriate when you need to list arrangements, preserve complete paths, or enforce constraints that depend on detailed history.

DP compresses paths that have the same future. If two partial arrangements share the same state but the output requires both arrangements, merging them loses required information. You might still use memoization to count or test feasibility, but not to enumerate distinct outputs without extra reconstruction logic.

DP versus divide and conquer#

Divide and conquer breaks a problem into smaller independent parts. Merge sort does not repeatedly sort the same exact range through different branches.

DP becomes useful when branches overlap. The distinction is not recursion itself. Both can use recursion. The distinction is whether identical subproblem inputs recur.

DP versus graph algorithms#

A DP state space is often an implicit directed graph. States are nodes. Recurrence transitions are edges.

If every transition has equal cost, breadth-first search may express a minimum-step problem more naturally. With nonnegative weighted transitions, a shortest-path algorithm may be a better fit. DP usually benefits from an acyclic dependency order, such as increasing indices or decreasing remaining capacity.

Worked Example: Recognizing House Robber as DP#

LeetCode 198, House Robber, is DP because each house creates a take-or-skip choice and different branches revisit the same suffix.

You receive a row of house values. You cannot rob adjacent houses. The goal is to maximize the collected value.

At house i, you have two choices:

1. Rob it. Gain nums[i], skip the adjacent house, and continue at i + 2.
2. Skip it. Gain nothing now and continue at i + 1.

Define best(i) as the maximum amount obtainable from house i onward. The direct recurrence is:

best(i) = max(nums[i] + best(i + 2), best(i + 1))

The base case is:

best(i) = 0 when i >= n

Where the repeated subproblems appear#

Start at best(0):

best(0)
├── nums[0] + best(2)
└── best(1)
    ├── nums[1] + best(3)
    └── best(2)

best(2) appears in two branches. Deeper levels repeat more suffix states. A plain recursive implementation recalculates those states.

The DP state needs only the index. It does not need a Boolean saying whether the previous house was robbed because the transitions already enforce the restriction: taking house i jumps to i + 2.

Bottom-up House Robber Python solution#

You can reverse the recurrence and retain only the next two state values:

def rob(nums):
    next_one = 0
    next_two = 0

    for value in reversed(nums):
        current = max(value + next_two, next_one)
        next_two = next_one
        next_one = current

    return next_one

Before each iteration:

• next_one represents the answer for the next house.
• next_two represents the answer for the house after that.
• current applies the recurrence for the current house.

The loop processes each house once, so the time complexity is O(n). It stores a fixed number of variables, so the auxiliary space complexity is O(1).

This optimization comes after the recurrence. First derive best(i). Then observe that each state reads only the next two states. Trying to jump directly to constant-space code makes the explanation harder and increases the chance of reversing the assignments.

How to Choose the Right DP State#

The right DP state contains exactly the information that can change future legal choices or future results.

Common state dimensions include:

• Index: where the unprocessed suffix begins.
• Remaining capacity: how much resource can still be used.
• Previous choice: what the next action is allowed to do.
• Interval boundaries: which contiguous region remains.
• Bitmask: which members of a small set have been used.
• Two indices: how much of two sequences has been processed.

Add a dimension only when two otherwise identical partial solutions have different futures.

For example, suppose two paths both reach index i. If one path used the previous element and the other did not, and that fact controls whether element i may be selected, then i alone is incomplete. You need dp(i, previous_used).

Sometimes you can remove that extra dimension by changing the transition. House Robber does this. After taking a house, it advances by two positions. The index then encodes everything the future needs.

To test whether two paths represent the same subproblem, ask:

1. Do they have the same available choices?
2. Will each future sequence of choices produce the same added value or validity?
3. Can the final answer ignore how each path arrived there?

If all three hold, merge them. If not, identify the missing distinction.

Unnecessary dimensions create more states, more initialization rules, and more opportunities for inconsistent transitions. A state such as dp(i, total_so_far) is often avoidable when the function can instead return the best additional value from i.

Top-Down or Bottom-Up in an Interview?#

Choose the implementation that makes your DP state and recurrence easiest to defend.

Start top-down when the recurrence is natural#

Memoized recursion often follows the decision tree directly. Each function parameter becomes a state dimension, and each branch becomes a recurrence transition.

It works well when:

• Only some theoretical states are reachable.
• The dependency order is awkward to derive.
• The recursive definition closely matches your explanation.
• You want to validate the recurrence before optimizing storage.

The trade-offs include recursive call overhead and recursion-depth limits. You must also ensure the cache key contains the complete state.

Use bottom-up when the order is clear#

Tabulation works well when you can identify a reliable evaluation order. It avoids recursion depth and often exposes space optimization.

It is especially useful when:

• Most states will be evaluated.
• Dependencies follow a simple index or interval order.
• You need explicit handling for unreachable states.
• Each state reads a small, fixed window of earlier states.

Initialization can be less intuitive than a recursive base case. State aloud what each table entry means and why the iteration order guarantees its dependencies are ready.

Neither approach changes the underlying DP state and recurrence. In an interview, it is reasonable to derive a top-down solution first and then convert it if the interviewer asks about stack usage or auxiliary space.

Common False Positives and DP Mistakes#

The most common failures come from choosing DP too early or defining a state that cannot support the recurrence.

Treating every optimization problem as DP#

A maximum or minimum objective is only a clue. Test greedy, graph, sorting, and direct mathematical approaches too.

If sorting exposes a simple invariant, use it. If a local choice has a proof, greedy may be cleaner. If states form a shortest-path problem, use that formulation.

Omitting information from the state#

A cache is correct only when equal keys mean equal subproblems. If future moves depend on remaining capacity, the previous action, or an unmatched balance, include that information.

Watch for a memoized function that reads mutable external state not represented in its key. Two calls may look identical to the cache while having different legal futures.

Writing code before the recurrence#

Code can hide a vague model behind indexes and conditionals. Write these items first:

• The exact meaning of dp(...).
• The choices available from that state.
• The transition for each choice.
• The base cases.
• The direction in which states become smaller.

Then implement those statements directly.

Using the wrong iteration order#

A bottom-up state must read completed dependencies. If dp[i] depends on dp[i + 1], iterate backward. If a capacity transition should prevent reusing an item, the capacity direction may matter.

Say the dependency before choosing the loop direction.

Mishandling unreachable states#

For minimum-cost DP, initializing every entry to zero can make impossible states look optimal. Use an explicit unreachable marker, such as infinity or a sentinel, and transition only from valid states.

Counting DP has a similar issue. Usually the empty construction has one way, while an unreachable nonempty target has zero ways. Those values are not interchangeable.

Accidentally leaving exponential recursion#

A recursive recurrence is not yet dynamic programming. Confirm that you cache every reusable state or convert the recurrence into a table.

Finally, hand-work small inputs before coding:

• An empty input.
• A single element.
• Two elements that force a choice.
• A case where the locally largest choice is not globally best.
• A case that reaches the same state through different paths.

Write the expected state values, not just the final answer. If the table or memoized calls disagree, fix the recurrence before debugging syntax. That habit is the practical core of learning how to spot a dynamic programming problem and turn it into code you can explain.