Dynamic programming (DP) is the topic that makes even experienced engineers freeze in a coding interview. The good news: DP is not a bag of tricks. It is a small number of patterns applied with a repeatable process. This guide gives you that process, the patterns that cover most interview questions, and a two-week plan to build fluency.
What Interviewers Are Really Testing
When a company asks a DP question, they are not checking whether you memorized the Fibonacci recurrence. They want to see whether you can identify overlapping subproblems, define state precisely, and reason about time and space trade-offs. A candidate who explains why a greedy approach fails and why memoization fixes it will beat one who silently writes a table.
A 5-Step Framework for Any DP Problem
1. Confirm DP applies
Look for optimal substructure (the best answer is built from best answers to smaller problems) and overlapping subproblems (the same smaller problem is solved repeatedly). Keywords like “minimum cost”, “number of ways”, “longest”, or “can you reach” are strong signals.
2. Define the state
Write one sentence: “dp[i] means …”. This single sentence is where most mistakes happen. If you cannot state it clearly, you do not yet understand the problem.
3. Write the transition
Express dp[i] in terms of earlier states. For climbing stairs it is dp[i] = dp[i-1] + dp[i-2]. For house robber it is dp[i] = max(dp[i-1], dp[i-2] + nums[i]).
4. Set base cases and order
Decide the initial values and the iteration order so every dependency is computed before it is used.
5. Optimize space
If dp[i] only depends on the previous one or two states, replace the array with a few variables.
Top-Down vs Bottom-Up
Start with a recursive solution plus memoization. It maps directly to how you think about the problem and is faster to get correct under pressure. Then, if time allows, convert to a bottom-up table and mention the space optimization. Interviewers value that you can move between both.
Pattern 1: 1D Linear DP
Classic problems: Climbing Stairs, House Robber, Min Cost Climbing Stairs, Decode Ways, Maximum Subarray. The state is a single index. Example in Java:
int rob(int[] nums) {
int prev = 0, curr = 0;
for (int n : nums) {
int next = Math.max(curr, prev + n);
prev = curr;
curr = next;
}
return curr;
}Notice the O(1) space. Stating this unprompted signals maturity.
Pattern 2: 0/1 Knapsack and Subset Sum
Problems such as Partition Equal Subset Sum, Target Sum, and Last Stone Weight II all reduce to “choose items to hit a capacity”. The state is dp[j] = whether sum j is reachable. Iterate the capacity backwards so each item is used once:
boolean canPartition(int[] nums) {
int total = Arrays.stream(nums).sum();
if (total % 2 != 0) return false;
int target = total / 2;
boolean[] dp = new boolean[target + 1];
dp[0] = true;
for (int n : nums)
for (int j = target; j >= n; j--)
dp[j] |= dp[j - n];
return dp[target];
}Pattern 3: Unbounded Knapsack
Coin Change and Combination Sum IV allow reusing items. The only change from 0/1 knapsack is iterating capacity forwards. Be ready to explain this difference; it is a favorite follow-up question.
Pattern 4: 2D Grid DP
Unique Paths, Minimum Path Sum, and Maximal Square use dp[r][c] built from the cell above and to the left. Always mention that you can compress to a single row.
Pattern 5: Two-Sequence DP
Longest Common Subsequence and Edit Distance use dp[i][j] over prefixes of two strings. Draw the table on the whiteboard, fill the first row and column, and explain each cell’s three possible moves. Edit Distance in particular shows whether you can reason about insert, delete, and replace as transitions.
Common Mistakes to Avoid
- Vague state definition. Say it out loud before coding.
- Wrong iteration direction in knapsack variants.
- Off-by-one errors in base cases. Test with an input of size 0 and 1.
- Jumping to optimization. Get a correct memoized solution first.
- Ignoring complexity. Always state time and space, e.g. O(n*W) time, O(W) space.
How to Communicate During the Interview
Start with brute-force recursion and its exponential complexity. Point out the repeated calls, then introduce memoization. This narrative shows you derived DP rather than recalled it. Finish with test cases, including edge cases like empty input and large values.
A 2-Week DP Practice Plan
Days 1-3: 1D DP (Climbing Stairs, House Robber, Decode Ways, Coin Change).
Days 4-6: Knapsack family (Partition Equal Subset Sum, Target Sum, Coin Change II).
Days 7-9: Grid DP (Unique Paths, Min Path Sum, Maximal Square).
Days 10-12: Two-sequence DP (LCS, Edit Distance, Longest Palindromic Subsequence).
Days 13-14: Timed mixed set. Solve 3 unseen problems in 45 minutes each, explaining aloud.
For every problem, write the state definition and transition in a notebook before looking at solutions. Revisit missed problems after 3 days to lock in the pattern.
Final Thoughts
DP rewards structured thinking over memorization. Learn the five patterns, apply the five-step framework, and practice explaining your reasoning aloud. Start today with one 1D problem, and build from there. If you want a structured way to rehearse, explore Niraswa AI and begin your preparation this week.
