Dynamic Programming: How to Identify the Problem Before Attacking It

The problem

Dynamic programming is often taught in the most hostile way possible.

They show a table.

They show a recurrence relation.

They show code that looks like it works by telepathy.

The person may even memorize two or three classic problems.

But when the question changes clothes, they freeze again.

The reason is simple:

they learned the ready-made solution, not how to recognize the type of problem.

Mental model

Dynamic programming is useful when the naive solution solves the same piece of the problem many times.

You notice that:

• there are smaller subproblems
• those subproblems repeat
• the answer for one state can be reused

In one short sentence:

DP is cache with criteria over repeated subproblems.

If there is no relevant repetition, it is probably not DP.

If the state is not clear, you probably still have not understood the problem.

Breaking the problem down

Question 1: what is being recalculated?

This is the best entry point.

If the naive recursive solution returns many times to the same scenario, that is a strong DP smell.

Common examples:

• the same position in the array with the same context
• the same index and the same remaining capacity
• the same pair of positions
• the same node with the same budget, steps, or restrictions

Question 2: what is the smallest state that matters?

State is the smallest amount of information needed to distinguish one answer from another.

This is the point that separates people who understood the problem from those who only memorized it.

Example:

• if the answer depends only on the current index, the state can be i
• if it depends on the index and remaining capacity, the state can be (i, cap)
• if it depends on two strings at different positions, the state can be (i, j)

If you put too much information into the state, the solution gets heavy.

If you put too little, the answer becomes wrong.

Question 3: how does one state come from smaller states?

This is where the transition appears.

You want to be able to say something like:

• “the answer here depends on the best choice between taking and not taking”
• “the answer for this cell comes from the best between top and left”
• “the answer at this point comes from the minimum cost among previous paths”

If you cannot explain the transition in simple English, you have not reached the solution yet.

Question 4: where does the recursion stop?

The base case is not a detail.

It is what gives ground to the rest.

Without a clear base case, the transition becomes a pretty formula sitting on nothing.

Memoization vs tabulation

Both techniques implement the same logic.

Memoization is usually:

• top-down
• more natural when you first think recursively
• good for starting from raw reasoning and then avoiding repetition

Tabulation is usually:

• bottom-up
• good when the order of states is clear
• useful for reducing recursive overhead and controlling space better

They are not rival schools.

They are two ways of walking through the same map.

Simple example

Take the question:

You can climb a staircase by taking 1 or 2 steps at a time. In how many different ways can you reach the top?

Naive solution

To reach step n, you can come from:

• n - 1
• n - 2

So someone writes pure recursion.

The problem is that ways(n - 2) appears many times in different branches.

And ways(n - 3) does too.

So you are recalculating the same subproblem unnecessarily.

The state

Here the minimum state is just:

• the current step n

The transition

The relation becomes:

• ways(n) = ways(n - 1) + ways(n - 2)

The base case

Something like:

• ways(0) = 1
• ways(1) = 1

That is enough.

Now you can solve it with memoization or tabulation.

The important point is not the staircase itself.

It is the logic:

• repeated subproblem
• minimum state
• transition
• base case

Where people get confused

Confusing DP with backtracking

Backtracking explores choices and returns.

DP reuses the answer for a state.

Sometimes a problem may even start from similar recursive reasoning, but the right question is different:

• do I need to explore combinations?
• or do I only need to compute the best value, quantity, or cost for repeated states?

Confusing DP with greedy

Greedy chooses the best local option hoping it closes globally.

DP compares possibilities across states.

If the local choice does not guarantee the global one, forcing greedy usually goes wrong.

Building the table too early

This is the most common mistake.

The person starts drawing a matrix without defining the state.

Then the table becomes decoration.

How a senior thinks

People with more practice do not start from “is this DP?”

They start from something more concrete:

• where am I repeating work?
• what distinguishes one subproblem from another?
• if I already knew this answer, what would I save?

That way of thinking is more robust because it also works outside interviews.

In real work, DP rarely appears under that name.

But the idea of:

• avoiding recomputation
• modeling state
• reusing partial results

shows up all the time.

What the interviewer wants to see

They want to see whether you:

• recognize repeated subproblems
• define sufficient state
• explain the transition without smoke
• choose a coherent implementation

If you say clearly “the recursive solution repeats scenarios; I will store the answer by state (i, j),” you already showed more understanding than someone who starts filling a pretty table without explaining anything.

Dynamic programming does not start in the table. It starts in the waste.

When you see the right state, half the problem is already smaller.