How do I know when a problem needs dynamic programming?

Question

I can solve DP problems when I know they're DP, but in contests I don't recognise them. Any signals?

Ankit Yadav · Accepted Answer

Two signals together:
1. **Choices at each step** (take/skip, go left/right) and you want a best or count.
2. **Overlapping subproblems**: the same state (index, remaining capacity) is reached in different ways.

Start with recursion, notice repeated calls, add memoisation. That's DP.

How do I know when a problem needs dynamic programming?

1 Answer

Log in to view all 1 Answer