Why DP Is The Most Feared (and Most Rewarding) Interview Topic
Dynamic Programming separates average engineers from strong ones in Indian SDE interviews. At MAANG companies, 1 in 3 coding problems involves DP. At Indian unicorns (Flipkart, Paytm, Groww, CRED), DP appears in roughly 1 in 5 rounds — more often as a medium-difficulty problem that can be solved once you recognize the pattern.
The good news: there are only 8–10 fundamental DP patterns. Once you master them, every DP problem becomes a variant you've seen before. This guide teaches you those patterns with 50+ real interview questions, solutions, and company frequency data.
The DP Truth Nobody Tells You
You don't need to solve 500 DP problems. You need to deeply understand 8 patterns and their recurrence relations. 50 well-chosen problems across these patterns will prepare you for 95% of DP questions in Indian SDE interviews.
The 5-Step DP Framework for Interviews
Use this framework every time you encounter a DP problem in an interview. State this framework out loud — interviewers love it.
1
Identify Type
Optimization? Counting? Existence? This determines the recurrence structure.
2
Define State
dp[i] means "..." — be precise. Wrong state = wrong solution.
3
Recurrence
Write dp[i] = f(dp[i-1], dp[i-2], ...). This is the core of DP.
4
Base Cases
What are dp[0], dp[1]? Off-by-one errors kill DP solutions.
5
Optimize Space
Can you reduce O(n²) space to O(n) or O(1)? Always discuss this.
Top-Down vs Bottom-Up
Top-down (memoization) = recursion + cache. Easier to write, may have stack overflow on large inputs. Bottom-up (tabulation) = iterative, faster in practice. In an interview, start with top-down for clarity, then mention the bottom-up optimization.
DP Patterns — All 10 with Problems
1
Fibonacci / Linear DP (1D)
Critical
Core idea: dp[i] depends on dp[i-1] and/or dp[i-2]. Often space-optimizable to O(1).
Recurrence template: dp[i] = dp[i-1] + dp[i-2] (or some variation)
-
E
Climbing Stairs (LC 70) dp[i] = dp[i-1] + dp[i-2]. Classic introduction to DP.
-
M
House Robber (LC 198) dp[i] = max(dp[i-2] + nums[i], dp[i-1]). Cannot rob adjacent.
-
M
House Robber II (LC 213) Circular array variant — solve twice, once excluding first, once excluding last.
-
M
Jump Game II — Minimum Jumps (LC 45) dp[i] = min jumps to reach index i. Also solvable with greedy O(n).
-
M
Decode Ways (LC 91) dp[i] = number of ways to decode string[0..i-1]. Handle leading zeros carefully.
// House Robber — O(n) time, O(1) space
int rob(int[] nums) {
int prev2 = 0, prev1 = 0;
for (int num : nums) {
int curr = Math.max(prev1, prev2 + num);
prev2 = prev1;
prev1 = curr;
}
return prev1;
}
2
0/1 Knapsack
Critical
Core idea: For each item, decide to include (use remaining capacity) or exclude. dp[i][w] = max value using first i items with capacity w.
Recurrence: dp[i][w] = max(dp[i-1][w], dp[i-1][w-wt[i]] + val[i])
-
M
0/1 Knapsack (classic) Foundation problem. Must code this from scratch in any interview.
-
M
Subset Sum (LC — Partition Equal Subset Sum 416) Can we partition array into 2 equal subsets? Reduce to knapsack with target = sum/2.
-
M
Target Sum (LC 494) Count ways to assign +/- to reach target. Count subsets with sum = (target + total)/2.
-
H
Last Stone Weight II (LC 1049) Partition into 2 groups, minimize difference. Classic knapsack with target = sum/2.
// 0/1 Knapsack — O(n*W) time, O(W) space (1D optimization)
int knapsack(int[] wt, int[] val, int W) {
int[] dp = new int[W + 1];
for (int i = 0; i < wt.length; i++) {
// Traverse right-to-left to avoid using item twice
for (int w = W; w >= wt[i]; w--) {
dp[w] = Math.max(dp[w], dp[w - wt[i]] + val[i]);
}
}
return dp[W];
}
3
Unbounded Knapsack
High Priority
Core idea: Same as 0/1 Knapsack but each item can be used unlimited times. Key difference: traverse left-to-right (not right-to-left).
-
M
Coin Change (LC 322) — Minimum coins dp[i] = min coins to make amount i. dp[i] = min(dp[i], dp[i-coin] + 1)
-
M
Coin Change II (LC 518) — Count combinations Count number of ways to make amount. dp[i] += dp[i-coin]
-
M
Integer Break (LC 343) Split n into parts to maximize product. dp[i] = max(j*(i-j), j*dp[i-j])
-
M
Perfect Squares (LC 279) Min perfect squares summing to n. Same as coin change with perfect square coins.
// Coin Change — Minimum coins (Unbounded Knapsack)
int coinChange(int[] coins, int amount) {
int[] dp = new int[amount + 1];
Arrays.fill(dp, amount + 1); // infinity sentinel
dp[0] = 0;
for (int i = 1; i <= amount; i++) {
for (int coin : coins) {
if (coin <= i)
dp[i] = Math.min(dp[i], dp[i - coin] + 1);
}
}
return dp[amount] > amount ? -1 : dp[amount];
}
4
Longest Common Subsequence (LCS)
Critical
Core idea: 2D DP on two strings/arrays. dp[i][j] = LCS of s1[0..i-1] and s2[0..j-1].
Recurrence: if s1[i-1]==s2[j-1]: dp[i][j] = dp[i-1][j-1]+1; else: max(dp[i-1][j], dp[i][j-1])
-
M
Longest Common Subsequence (LC 1143) Foundation. Master this and most string DP becomes easy.
-
M
Edit Distance (LC 72) Minimum insert/delete/replace to convert s1 to s2. LCS variant.
-
M
Shortest Common Supersequence (LC 1092) len(SCS) = len(s1) + len(s2) - LCS(s1, s2)
-
M
Longest Common Substring (different from LCS!) Characters must be contiguous. dp[i][j] = dp[i-1][j-1]+1 only if chars match, else 0.
-
M
Minimum Insertions to Make String Palindrome n - LCS(s, reverse(s)). Elegant LCS application.
5
Longest Increasing Subsequence (LIS)
High Priority
Core idea: dp[i] = length of LIS ending at index i. Standard solution O(n²), optimized with patience sorting O(n log n).
-
M
Longest Increasing Subsequence (LC 300) dp[i] = max(dp[j]+1) for all j<i where nums[j]<nums[i]
-
M
Russian Doll Envelopes (LC 354) Sort by width asc, height desc. Then LIS on heights only.
-
M
Longest Bitonic Subsequence LIS from left + LIS from right - 1. Classic variant.
-
M
Maximum Sum Increasing Subsequence Same as LIS but maximize sum, not length.
6
Grid / Matrix DP
High Priority
Core idea: Navigate a 2D grid. dp[i][j] = optimal value to reach cell (i,j). Transitions typically from dp[i-1][j] and dp[i][j-1].
-
M
Unique Paths (LC 62) dp[i][j] = dp[i-1][j] + dp[i][j-1]. Foundation grid DP.
-
M
Minimum Path Sum (LC 64) dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])
-
M
Triangle (LC 120) Bottom-up: dp[i][j] = triangle[i][j] + min(dp[i+1][j], dp[i+1][j+1])
-
H
Maximal Square (LC 221) dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1 if grid[i][j]=='1'
-
H
Cherry Pickup (LC 741 / 1463) Two robots collecting simultaneously. 3D DP or 2D with clever state.
7
String / Palindrome DP
High Priority
Core idea: Often involves checking if a substring is a palindrome, or optimal way to partition a string.
-
M
Longest Palindromic Subsequence (LC 516) LCS(s, reverse(s)). Or 2D DP: dp[i][j] = LPS of s[i..j]
-
M
Longest Palindromic Substring (LC 5) Expand around center O(n²) or DP table. Both are valid approaches.
-
H
Palindrome Partitioning II (LC 132) Min cuts to make all parts palindromes. Precompute isPalin[i][j] then DP.
-
M
Word Break (LC 139) dp[i] = true if s[0..i-1] can be segmented. dp[i] = OR(dp[j] && dict.has(s[j..i-1]))
8
Interval / Partition DP
Medium Priority
Core idea: Optimal way to split a range [i..j]. Enumerate every split point k in [i..j-1]. Common in matrix chain, balloon burst problems.
-
H
Burst Balloons (LC 312) dp[i][j] = max coins from bursting all balloons between i and j. Think "last to burst."
-
H
Strange Printer (LC 664) Minimum turns to print string. If s[i]==s[j], dp[i][j] = dp[i][j-1].
-
H
Matrix Chain Multiplication (classic) dp[i][j] = min cost to multiply matrices i to j. Try all split points k.
-
H
Minimum Cost to Cut a Stick (LC 1547) Similar to matrix chain — enumerate all cut positions.
9
DP on Trees
Medium Priority
Core idea: DP state is defined per node. Child states bubble up to parent. Often involves choosing to include/exclude a node.
-
M
House Robber III (LC 337) Rob a tree — cannot rob parent and child. dp per node: (rob, not rob).
-
M
Diameter of Binary Tree (LC 543) At each node: longest path = leftHeight + rightHeight. Update global max.
-
H
Binary Tree Maximum Path Sum (LC 124) Path can start/end anywhere. At each node: max(left, 0) + val + max(right, 0).
10
DP with Bitmask
FAANG / Hard
Core idea: State includes a bitmask representing which elements have been used. Common in TSP, assignment problems. O(2^n * n) complexity.
-
H
Traveling Salesman Problem (TSP) dp[mask][i] = min cost to visit nodes in mask, ending at node i.
-
H
Shortest Path Visiting All Nodes (LC 847) BFS + bitmask. State = (node, visited_bitmask).
-
H
Partition to K Equal Sum Subsets (LC 698) Bitmask DP or backtracking with pruning. O(n * 2^n).
Company-wise DP Frequency
| Company | DP Frequency | Most Common Patterns | Avg Difficulty |
|---|---|---|---|
| Very High | Interval DP, Bitmask, LCS, Grid | Hard | |
| Amazon | High | Knapsack, LCS, LIS, Fibonacci | Medium |
| Microsoft | High | Fibonacci, Grid, String DP | Medium |
| Flipkart | High | LCS, Knapsack, LIS | Medium |
| Groww | High | Grid DP, LCS, Trees DP | Medium–Hard |
| Paytm | Medium | Fibonacci, Coin Change, LCS | Medium |
| Meesho | Medium | Fibonacci, Knapsack basics | Easy–Medium |
| CRED | Medium | String DP, LCS, Palindrome | Medium |
| PhonePe | Medium-Low | Fibonacci, Coin Change | Easy–Medium |
| Zomato | Medium-Low | Grid DP, Fibonacci | Medium |
Master DP with AI-powered practice
Start Free Trial on PrepflixTop 6 DP Mistakes in Interviews
Mistake 1: Wrong state definition
"dp[i] = maximum value" is too vague. Be precise: "dp[i] = maximum value considering elements from index 0 to i, where element i is included." A wrong state definition means a wrong recurrence, which means a wrong solution.
Mistake 2: Not handling base cases
Off-by-one errors in base cases are the #1 cause of wrong DP answers. Always trace through dp[0] and dp[1] manually before coding.
Mistake 3: Jumping to bottom-up without clarity
If you're not 100% sure of the recurrence, start with top-down (memoization). It's easier to visualize and debug. Convert to bottom-up only once the logic is clear.
Mistake 4: Not stating the recurrence aloud
Interviewers want to hear your thought process. Always say "dp[i] equals..." before writing any code. Silent coding is a red flag.
Mistake 5: Forgetting space optimization
After the correct O(n²) solution, always mention: "This can be optimized to O(n) space by using rolling arrays." Even if you don't implement it, stating this shows depth.
Mistake 6: Using DP when greedy works
Some problems look like DP but have greedy solutions (Jump Game, Activity Selection). If you can prove a greedy choice is always safe, use greedy — it's simpler and faster.
30-Day DP Study Plan
| Week | Patterns | Problems | Daily Target |
|---|---|---|---|
| Week 1 | Fibonacci DP, 0/1 Knapsack | Climbing Stairs, House Robber, Coin Change, Subset Sum, Target Sum | 2–3 problems/day |
| Week 2 | LCS, LIS, String DP | LCS, Edit Distance, LIS, Palindrome Partitioning, Word Break | 2–3 problems/day |
| Week 3 | Grid DP, Tree DP | Unique Paths, Min Path Sum, Maximal Square, House Robber III, Tree Max Path | 2–3 problems/day |
| Week 4 | Interval DP, Review + Mocks | Burst Balloons, Matrix Chain, 3 full mock contests, review weak patterns | 2 problems + 1 mock |
The 50 Essential DP Problems
For Indian SDE interviews, master these in order: Climbing Stairs → House Robber → Coin Change → LCS → Edit Distance → LIS → Unique Paths → Min Path Sum → Longest Palindromic Subsequence → Word Break → Knapsack → Burst Balloons. Everything else is a variant.
Frequently Asked Questions
What DP patterns appear most in Indian SDE interviews?
The most common DP patterns in Indian SDE interviews are: 1D Fibonacci DP, Knapsack (0/1 and Unbounded), LCS, LIS, and Grid DP. These 5 patterns cover about 70% of DP questions at top Indian companies.
How many DP problems should I solve before an interview?
Solve 50–60 DP problems across 8–10 key patterns. Quality matters more than quantity — understand the pattern, not just the solution. For FAANG/MAANG, focus on hard DP. For Indian unicorns like Flipkart, Meesho, Paytm, medium DP is sufficient.
Is DP asked in SDE-1 interviews?
Yes, DP is asked at SDE-1 level but typically medium difficulty — Coin Change, Climbing Stairs, Knapsack, and LCS variants. Hard DP (Burst Balloons, Matrix Chain) is more common in SDE-2+ and FAANG interviews.
Which company asks the most DP questions?
Amazon and Google ask the most DP questions in Indian SDE interviews. Groww and Flipkart also have strong DP tracks. Meesho and Paytm ask fewer hard DP problems, focusing more on medium-level array/HashMap/string questions.
What is the best strategy to approach a DP problem in an interview?
Use the 5-step framework: (1) Identify the type (optimization/counting/existence). (2) Define the state clearly. (3) Write the recurrence relation. (4) Decide top-down vs bottom-up. (5) Optimize space. Always start with brute-force recursion and memoize step by step.
