9. What is dynamic programming and how do you recognise a DP problem?
MediumData structures & algorithms
Technical
Show model answer
Dynamic programming solves a problem by combining answers to overlapping subproblems and storing them so each is computed once, either top-down with memoisation or bottom-up with a table.
Signs of DP: the question asks for a count, a minimum or a maximum over many choices, and a brute-force recursion recomputes the same states. Define the state, the recurrence and the base cases, then optimise memory if only recent states are needed.
What interviewers listen for
- State, transition, base case
- Memoisation vs tabulation
- Watch for greedy shortcuts that fail