Skip to interview prep
Apexed

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
What is dynamic programming and how do you recognise a DP problem — Software engineering interview question — Apexed