A strong answer
Dynamic programming solves a problem by combining solutions to subproblems, computing each distinct subproblem once and reusing it. It applies when two properties hold: optimal substructure, meaning the answer can be built from answers to smaller instances of the same problem, and overlapping subproblems, meaning the same instances recur many times in a naive recursion.
Merge sort has optimal substructure but no overlap, since each subarray is sorted once: that is divide and conquer. Greedy algorithms make one choice per step and never revisit it; DP considers every choice for the last step and keeps the best, which is why it succeeds where greedy fails, for example coin change with coins 1, 3 and 4.
Signals in a problem: it asks for a count, a minimum or maximum, or whether something is possible; it involves choices at each step; and a brute-force recursion branches on those choices with repeated arguments.
My method: define the state in words, the smallest description of a subproblem (for example "dp[i] is the best for the first i items"); write the recurrence by considering the last decision; set base cases; choose an order where dependencies come first; and identify where the answer is. The cost is the number of states times the work per state. I usually write it top-down with memoization first, then convert to a table if recursion depth or memory requires it.
What the interviewer is listening for
- Both properties, with examples of each missing.
- The difference from divide and conquer and from greedy.
- A concrete design method and the states × work cost formula.
Common mistakes
- Defining DP as "recursion with a cache" without the conditions that make it valid.
- Vague states, which lead to wrong recurrences.
- Forgetting that memoization needs a pure function of the arguments.