Recognizing a dynamic-programming problem
“How do you recognize that a problem needs dynamic programming, and how do you go from recognition to a working solution?”
What this tests
- Whether the candidate knows the two properties (optimal substructure, overlapping subproblems) and can *check* them, not just name them.
- Whether they define the state before the transition and can justify that the state is sufficient.
- Ability to derive complexity as states × transition cost.
- Knowing when DP is inappropriate (no overlap → plain recursion or divide and conquer; greedy suffices).
Strong answer
The surface signals: "number of ways", "minimum cost", "maximum value", "is it possible", over a sequence of choices where each choice constrains later ones; constraints small enough for a polynomial state space (n ≤ 5000, or n ≤ 20 for bitmask); and a brute-force recursion that would revisit the same situation many times. But a strong candidate verifies two properties rather than trusting the phrasing. Optimal substructure: the optimal answer for the whole is built from optimal answers to subproblems — if the best answer for a prefix might require a *suboptimal* answer for a shorter prefix, DP does not apply. Overlapping subproblems: the recursion tree contains the same subproblem repeatedly; if not, plain recursion or divide and conquer is already efficient.
From recognition to solution is a fixed procedure. 1. Write the brute-force recursion — what decision is made at each step, what information the rest of the problem needs. 2. Name the state: the minimal set of parameters that determine the answer to the remainder. This is the hard step; "index i" is the state for House Robber, "index and remaining capacity" for 0/1 Knapsack, "pair of indices" for Longest Common Subsequence, "index and previous element" for Longest Increasing Subsequence. If the state grows unboundedly, DP is wrong or the state is wrong. 3. Write the transition from the choices. 4. Identify base cases and order — memoize top-down, or tabulate in an order where dependencies are already computed. 5. Complexity: number of states × work per transition. 6. Reconstruct the choice if the problem wants the solution, not just the value.
They also know what DP is structurally: shortest path on the DAG of states. That view explains why cyclic dependencies mean the state is wrong, why the topological order of tabulation matters, and why a problem with a greedy choice property can skip DP entirely. And they check for the failure mode of "DP for everything": if n = 10^5 and the state would be O(n^2), they look for a monotonic-queue or segment-tree optimization or a different formulation.
Green flags · Red flags
- Checks optimal substructure with a concrete "does the optimal whole use an optimal part?" argument.
- Defines the state and argues it is sufficient before writing a transition.
- Writes the brute-force recursion first, then memoizes.
- Computes complexity as states × transition.
- Says when DP is the wrong tool: no overlap, greedy suffices, or state space too large for the constraints.
- Mentions reconstructing the solution, not just the value.
- Starts filling a table without saying what a cell means.
- Cannot say why the problem has overlapping subproblems.
- Uses a state that omits information the remainder depends on (e.g., LIS without the previous element or its equivalent).
- Believes every optimization problem is DP.
- Gives complexity as "
O(n)because it is one loop" while the transition isO(n).
Follow-up questions
Each follow-up changes a requirement; the right answer changes with it.
A" and its complexity.O(n log n)?