Dynamic programming interview questions
Dynamic programming has a reputation for being clever. In interviews it is a method: define what you are computing, write how a bigger answer is built from smaller ones, and avoid recomputing.
How do I solve dynamic programming interview questions?
Dynamic programming solves a problem by breaking it into overlapping subproblems and storing each answer once. Define the state, write the recurrence that builds a larger answer from smaller ones, set the base cases, then use memoised recursion or a table, and state the time as the number of states times the work per state.
How to recognise a dynamic programming problem
The question asks for a count of ways, a minimum or maximum, or whether something is possible, over choices made step by step.
A recursive solution exists but recomputes the same arguments many times.
Typical shapes: climbing stairs, coins, subsequences, knapsack, grids of paths, edit distance, partitioning a string.
How to build the solution
Write the brute-force recursion first. Name its arguments: they are the state, for example (index, remaining amount).
Add a cache keyed by the state (memoisation). The number of distinct states times the work inside each call is the running time.
If you want to avoid recursion depth, convert to a table filled in dependency order, and see whether you only need the last row or two, which reduces the memory.
State the recurrence and base cases out loud before coding, for example ways(n) = ways(n - 1) + ways(n - 2) with ways(0) = 1 and ways(1) = 1.
Classic problems to practise
Climbing Stairs, House Robber, Coin Change, Longest Increasing Subsequence, Longest Common Subsequence, Unique Paths, Word Break, Partition Equal Subset Sum, Edit Distance.
Mistakes interviewers see
Starting with a table and an unclear state. Begin with the recursion; the state follows from its arguments.
A state that is too small to determine the answer, or too large to be fast. Check both.
Wrong base cases and off-by-one indexes, especially for the empty prefix.
Greedy mistaken for dynamic programming, or the reverse. If a locally best choice is provably safe, say so; otherwise try the options.
Practise it as an interview
Take a topic-based interview on dynamic programming to practise the pattern the way it is asked: say the pattern before you code, write and run the solution in a live editor, and answer the cross-questions about edge cases and complexity. The scored report shows whether you lost points explaining, coding or defending. Your first 3 single-question interviews are free for life, every interview report is free, and a new account also gets 6 welcome credits.
Frequently asked questions
Memoisation or tabulation?
Memoisation (top-down) is faster to write and only computes the states you need. Tabulation (bottom-up) avoids recursion limits and makes space optimisation easier. Either is acceptable if you explain the state.
How do I know it is dynamic programming and not greedy?
If different earlier choices lead to the same later situation and you cannot prove a locally best choice is safe, dynamic programming is the safer approach.