When it applies
Two conditions:
Overlapping subproblems - the same sub-computation recurs many times. Optimal substructure - the optimal solution is built from optimal solutions to subproblems.
If both hold, you can memoise or tabulate and turn exponential into polynomial.
The process
- Define the state. What does the subproblem depend on? This is where almost all errors happen.
- Write the recurrence relating a state to smaller ones.
- Identify the base cases.
- Choose direction - top-down memoised recursion is easier to write; bottom-up tabulation avoids stack depth and is usually faster.
- Check the complexity - typically number of states times work per state.
The connection to probability
This is worth noticing, because it makes quant DP questions easier than they look.
The expected-value recursions and Markov chain hitting times you use in probability questions are dynamic programming. Defining states for a coin-pattern problem is the same exercise as defining states for a DP.
So an interviewer asking you to compute the expected number of flips to see HTH, and one asking for a DP over strings, are testing the same skill.
Classic patterns
- 1D over an index: house robber, maximum subarray, climbing stairs.
- 2D over two sequences: edit distance, longest common subsequence.
- Knapsack: capacity as a dimension of state.
- Interval DP: matrix chain, optimal binary search trees.
- Bitmask DP: small sets, exponential in set size but tractable for n up to about 20.
Getting the state right
If your recurrence produces inconsistent results, the state is almost always underspecified - you are missing something that the future depends on. That is the exact same diagnosis as a process that is not Markov in the state you chose.
Space optimisation
Many 1D DPs only need the previous row or two, reducing O(n) space to O(1). Mentioning this after producing a correct solution is a good closing move.
Practise in programming and DSA.