How to tell a problem needs DP

Dynamic programming Mid-level Python 3.13+ Reviewed By Best Latest Apps

Pick the fix

Which question is the best fit for DP?

Options

Choose an answer, then open Show answer below to check it.

Show answer

Answer: A Count the ways to pay 50 with coins 1, 2 and 5

Right: counting over choices, with repeated sub-amounts.

Counting can reuse sub-answers without writing each combination down, which is where DP wins.

Why not the others?
  • B List every way to pay 50 with coins 1, 2 and 5. Listing needs every answer written out: backtracking.
  • C Pay 50 with the fewest coins from 1, 2, 5, 10, 20. That coin system works greedily, so DP is unnecessary.

30-second answer

Look for three things: you make a sequence of choices, the question asks for a best value or a count over all choices, and different choice sequences lead to the same sub-question. If a simple local rule always works (with a proof), greedy is enough. If you must list every answer, backtracking is needed. If sub-questions repeat, cache them: that is DP.

Practise saying it · 30 s. No recording, just a timer

Explain how you recognise DP.

Say your answer out loud, then check which of these points you covered:

  • Choices
  • Best value or count
  • Repeated sub-questions

Deep dive

Words like 'number of ways', 'minimum cost', 'longest', 'can you reach' are common signals.

Try a small counterexample against greedy before committing to it.

Input limits help: n up to a few thousand with two dimensions suggests O(n²) DP.

Common mistakes

  • Reaching for DP when a greedy choice is provably optimal.
  • Using DP when the question asks to list all answers, whose count can be exponential.

Senior take & follow-ups

Name the signals you see in the question out loud.

Follow-up questions

Think of your answer first, then open the hint.

  1. How do you prove greedy is safe?

    Show hint

    An exchange argument: any optimal answer can be changed to include the greedy choice without getting worse.

  2. What if the state space is too big?

    Show hint

    Look for a monotonic property to binary search, or a different state.

What each operation costs: Two Dimensional Arrays

From the author

DSA Master - Data & Algorithms

Free on iPhone and iPad: watch 50+ data structures and algorithms step through animations, run the code in the playground, and try the daily challenge.

Get it on the App Store

Suggest a fix if something here is wrong or out of date.