| Fibonacci / Climbing Stairs | 1D DP — O(n) time, O(1) space with two rolling variables |
| Longest Common Subsequence | 2D DP on two strings — O(m×n) time and space, reducible to O(n) space |
| Edit Distance | 2D DP — O(m×n) time and space, insert/delete/replace transitions |
| 0/1 Knapsack | 2D DP (items×capacity) — O(n×W) time, space-optimizable to 1D (right-to-left) |
| Unbounded Knapsack / Coin Change | 1D DP over capacity — O(n×W) time, ascending (left-to-right) inner loop |
| Longest Increasing Subsequence | O(n²) DP, or O(n log n) with patience sorting / binary search |
| Matrix Chain Multiplication | Interval DP — O(n³) time, O(n²) space, minimize scalar multiplications |
| Palindrome Partitioning | Interval DP + precomputed O(n²) palindrome table for O(n²) cuts |
Dynamic Programming Interview Questions & Answers
Q1. What is dynamic programming and why is it used in algorithm design?
A: Dynamic programming (DP) is a technique for solving problems by breaking them into smaller subproblems, solving each subproblem once, and storing (caching) its result so it is never recomputed. It applies when a problem has optimal substructure and overlapping subproblems — properties that make naive recursion redundantly re-solve the same subproblem exponentially many times. By trading extra memory for reused work, DP typically turns an exponential brute-force solution into a polynomial-time one.
Q2. What are the two core properties a problem must have to be solved with DP?
A: A problem is a DP candidate if it has optimal substructure (the optimal solution to the whole problem can be built from optimal solutions to its subproblems) and overlapping subproblems (the same subproblem is encountered repeatedly during a naive recursive solve). If a problem has optimal substructure but no overlapping subproblems, plain divide-and-conquer already handles it efficiently and caching adds no benefit.
Q3. What is optimal substructure, precisely?
A: A problem exhibits optimal substructure when an optimal solution to it can be constructed directly from optimal solutions to its smaller subproblems — you never need a suboptimal subproblem answer to build the overall optimum. For example, the shortest path from A to C through B is the shortest A-to-B path plus the shortest B-to-C path; you never need a non-shortest sub-path to form the shortest overall path.
Q4. What are overlapping subproblems, and how do they differ from divide-and-conquer's subproblems?
A: Overlapping subproblems means the recursive breakdown revisits the exact same subproblem (same parameters) many times — for example, naive Fibonacci recomputes fib(2) repeatedly across different call branches. In classic divide-and-conquer (like merge sort), the subproblems are disjoint slices of the input, so no subproblem is ever solved twice, which is why merge sort doesn't benefit from memoization while Fibonacci does.
Q5. What is the difference between memoization (top-down) and tabulation (bottom-up)?
A: Memoization keeps the natural recursive structure but adds a cache (array or map) that stores each subproblem's result the first time it's computed, returning the cached value on later calls — you only compute what's actually needed. Tabulation instead builds an explicit table iteratively from the base cases upward, filling every state in a fixed order until the answer is reached, with no recursion or call-stack usage at all.
Q6. What are the trade-offs between top-down and bottom-up DP?
A: Top-down memoization is often easier to derive directly from the brute-force recursion and naturally skips states that are never actually needed, but it carries recursion call-stack overhead and risks stack overflow on deep recursion. Bottom-up tabulation avoids recursion entirely (safer for large inputs) and is usually a bit faster due to no function-call overhead, but it computes every state in the table even if some are unreachable, and the correct fill order must be worked out explicitly.
Q7. How do you recognize that an interview problem is a DP problem?
A: Look for phrases like "minimum/maximum number of ways," "count the number of ways," "is it possible to reach/partition," or optimization over choices made at each step (take it or skip it, cut here or there). A strong signal is that a brute-force recursive solution is easy to write but clearly re-explores identical subproblems — if you can express the answer for input size n in terms of answers for smaller inputs, it's very likely DP.
Q8. What are the concrete steps to convert a brute-force recursive solution into a DP solution?
A: First, write the correct (even if slow) recursive solution and identify its state — the minimal set of parameters that uniquely determines a subproblem. Second, verify overlapping subproblems exist (the same state recurs). Third, add a cache keyed by that state (memoization) or restructure the recursion into an iterative fill order (tabulation), being careful that every state a transition depends on is computed before it's needed.
// Step 1: brute-force recursion (state = n)
int solve(int n) {
if (n <= 1) return n;
return solve(n - 1) + solve(n - 2);
}
// Step 2/3: add a cache keyed by state
Integer[] memo = new Integer[100];
int solveMemo(int n) {
if (n <= 1) return n;
if (memo[n] != null) return memo[n];
return memo[n] = solveMemo(n - 1) + solveMemo(n - 2);
}Q9. What is "state" in dynamic programming?
A: The state is the minimal set of variables that fully describes a subproblem — enough information to compute its answer without needing anything about how you arrived there. For Fibonacci the state is just n; for LCS it's a pair of indices (i, j) into the two strings; for knapsack it's (item index, remaining capacity). Choosing the right state is the central design decision in any DP solution, since it determines the table's dimensions and size.
Q10. What is a recurrence relation / state transition in DP?
A: The recurrence relation expresses how to compute the answer for a state in terms of the answers to one or more smaller (already-solved) states — for example, dp[i] = dp[i-1] + dp[i-2] for Fibonacci, or dp[i][j] = dp[i-1][j-1] + 1 when characters match in LCS. Deriving the recurrence correctly, including all base cases, is the crux of designing any DP solution.
Q11. How do you determine the time complexity of a DP solution in general?
A: Time complexity is (number of distinct states) × (work done per state to compute its transition). For a 1D DP over n with O(1) transitions, that's O(n); for a 2D DP over m×n states each combining O(k) prior states (like matrix chain's interval split), it's O(m×n×k). Counting states and transition cost separately is the fastest way to reason about DP complexity in an interview.
Q12. How do you determine the space complexity of a DP solution, and when can it be reduced?
A: Space complexity is generally the size of the DP table needed to store all computed states — O(n) for 1D, O(m×n) for 2D. It can often be reduced when the recurrence for a state only depends on the immediately previous row/column (not the entire history), letting you keep just one or two rolling rows instead of the full table — cutting a 2D O(m×n) table down to O(n) or O(min(m,n)).
Q13. Why does plain recursion for Fibonacci run in exponential time?
A: Each call to fib(n) spawns two more calls, fib(n-1) and fib(n-2), and this branching continues down to the base cases, forming a call tree with roughly 2ⁿ nodes. Because fib(n-2) is computed independently inside both the fib(n-1) branch and directly, the same values are recomputed exponentially many times — precisely the overlapping-subproblems symptom that memoization fixes, dropping the runtime to O(n).
Q14. Why do base cases matter so much in DP, and what happens if they're wrong?
A: Base cases anchor the entire recurrence — every other state is ultimately built up from them, so an incorrect or missing base case silently corrupts every dependent state without throwing any error. A classic bug is forgetting the empty-string or empty-array base case in a 2D string DP (row/column 0), which produces subtly wrong answers only visible on edge-case inputs like an empty input or a single-character string.
Q15. How do you decide the correct order to fill a DP table?
A: The fill order must guarantee that every state a transition reads from has already been computed — in practice, this means iterating in the direction the recurrence "points." A recurrence like dp[i][j] depending on dp[i-1][j], dp[i][j-1], and dp[i-1][j-1] requires filling rows top to bottom and columns left to right; interval DP (like matrix chain) requires iterating by increasing subproblem length rather than by raw index.
Q16. What is the difference between DP and greedy algorithms?
A: A greedy algorithm makes one irrevocable locally-optimal choice at each step and never reconsiders it, which only produces a globally optimal answer when the problem has the "greedy choice property." DP instead considers the outcomes of all viable choices at each state (often implicitly, via the recurrence's max/min over transitions) and combines them, which is necessary whenever a locally optimal choice can lead to a globally suboptimal result — e.g., 0/1 knapsack requires DP while fractional knapsack can be solved greedily.
Q17. What is the difference between DP and divide-and-conquer?
A: Both break a problem into subproblems and combine their results, but divide-and-conquer's subproblems are independent and non-overlapping (like the two halves in merge sort), so nothing is gained from caching. DP's subproblems overlap — the same subproblem reappears via different paths through the recursion — which is exactly what makes caching (memoization/tabulation) valuable for DP but pointless for classic divide-and-conquer.
Q18. When does a DP approach fail to give the optimal answer, i.e. when should you not use DP?
A: DP itself doesn't "fail" to be correct if the recurrence is right, but it's the wrong tool when a problem lacks optimal substructure (no way to build the global optimum from subproblem optima) or when the state space is too large to enumerate (e.g., some NP-hard problems have exponential state spaces even with memoization, like general TSP for large n). In those cases, approximation algorithms, greedy heuristics, or branch-and-bound are used instead.
Q19. What is the recursive (exponential) solution to Fibonacci, and why is it slow?
A: The direct recursive translation of the definition fib(n) = fib(n-1) + fib(n-2) recomputes the same smaller Fibonacci values many times across different branches of the call tree, giving O(2ⁿ) time with no caching at all. It is correct but impractical beyond roughly n=40 in an interview setting because the redundant work grows exponentially.
int fib(int n) {
if (n <= 1) return n;
return fib(n - 1) + fib(n - 2);
}Q20. How do you solve Fibonacci with top-down memoization in Java?
A: Wrap the same recursive definition with a cache (array or HashMap) keyed by n; before recursing, check whether the value is already cached and return it immediately if so. This turns the O(2ⁿ) exponential blow-up into O(n) time and O(n) space, since each distinct n is now computed exactly once.
Map<Integer, Long> memo = new HashMap<>();
long fib(int n) {
if (n <= 1) return n;
if (memo.containsKey(n)) return memo.get(n);
long result = fib(n - 1) + fib(n - 2);
memo.put(n, result);
return result;
}Q21. How do you solve Fibonacci with bottom-up tabulation in Java?
A: Allocate a table of size n+1, seed dp[0] and dp[1] with the base cases, then iterate from i=2 upward, computing each dp[i] from the two previous entries. This is O(n) time, O(n) space, and avoids recursion and call-stack overhead entirely.
long fib(int n) {
if (n <= 1) return n;
long[] dp = new long[n + 1];
dp[0] = 0; dp[1] = 1;
for (int i = 2; i <= n; i++) dp[i] = dp[i - 1] + dp[i - 2];
return dp[n];
}Q22. How do you further reduce Fibonacci's space to O(1)?
A: Since each state only ever depends on the two immediately preceding values, there's no need to keep the entire table — just track two rolling variables and update them each iteration. This is the canonical example of state-space optimization: same O(n) time, but O(1) space instead of O(n).
long fib(int n) {
if (n <= 1) return n;
long prev2 = 0, prev1 = 1;
for (int i = 2; i <= n; i++) {
long curr = prev1 + prev2;
prev2 = prev1;
prev1 = curr;
}
return prev1;
}Q23. How do you solve the Climbing Stairs problem with DP?
A: To reach step n, your last move was either a single step from n-1 or a double step from n-2, so the number of distinct ways is ways(n) = ways(n-1) + ways(n-2) — structurally identical to Fibonacci. It can be solved with O(n) tabulation or reduced to O(1) space with two rolling variables, since only the previous two counts are ever needed.
int climbStairs(int n) {
if (n <= 2) return n;
int prev2 = 1, prev1 = 2;
for (int i = 3; i <= n; i++) {
int curr = prev1 + prev2;
prev2 = prev1;
prev1 = curr;
}
return prev1;
}Q24. How do you generalize Climbing Stairs to allow taking 1..k steps at a time?
A: The recurrence becomes dp[i] = dp[i-1] + dp[i-2] + ... + dp[i-k], summing over the last k possible step sizes instead of just the last two. This costs O(n×k) time with a naive inner loop, but can be optimized to O(n) using a sliding-window sum that adds the new term entering the window and subtracts the one leaving it, exactly like the sliding-window-sum technique used for array problems.
Q25. How do you solve Min Cost Climbing Stairs?
A: Define dp[i] as the minimum cost to reach step i; you can arrive at step i from step i-1 or step i-2, paying that step's cost, so dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2]). The answer is dp[n], and the base cases are dp[0] = dp[1] = 0 since you can start from either of the first two steps for free.
int minCostClimbingStairs(int[] cost) {
int n = cost.length;
int prev2 = 0, prev1 = 0;
for (int i = 2; i <= n; i++) {
int curr = Math.min(prev1 + cost[i - 1], prev2 + cost[i - 2]);
prev2 = prev1;
prev1 = curr;
}
return prev1;
}Q26. How do you solve the House Robber problem?
A: At each house, you either rob it (adding its value to the best total that excluded the previous house) or skip it (keeping the best total up to the previous house either way). Tracking two rolling values — best total if the previous house was taken, and best total if it wasn't — gives O(n) time and O(1) space without needing a full DP array.
int rob(int[] nums) {
int prevNoTake = 0, prevTake = 0;
for (int num : nums) {
int currTake = prevNoTake + num;
int currNoTake = Math.max(prevTake, prevNoTake);
prevTake = currTake;
prevNoTake = currNoTake;
}
return Math.max(prevTake, prevNoTake);
}Q27. How does House Robber II (houses arranged in a circle) differ from House Robber I?
A: Because the first and last houses are now adjacent, robbing both is disallowed, so the problem splits into two independent linear House Robber subproblems: one excluding the last house, one excluding the first, and the answer is the max of the two. This handles the circular constraint without changing the core linear DP logic.
int robCircular(int[] nums) {
int n = nums.length;
if (n == 1) return nums[0];
return Math.max(robLinear(nums, 0, n - 2), robLinear(nums, 1, n - 1));
}
int robLinear(int[] nums, int start, int end) {
int prevNoTake = 0, prevTake = 0;
for (int i = start; i <= end; i++) {
int currTake = prevNoTake + nums[i];
int currNoTake = Math.max(prevTake, prevNoTake);
prevTake = currTake;
prevNoTake = currNoTake;
}
return Math.max(prevTake, prevNoTake);
}Q28. How do you solve House Robber III, where houses are arranged as a binary tree?
A: This is DP on a tree: for each node, compute two values via post-order traversal — the best total if this node is robbed (its value plus both children's "not robbed" totals, since adjacent nodes can't both be taken) and the best total if it's not robbed (sum of each child's max of robbed/not-robbed). The answer at the root is the max of its two values, computed bottom-up in O(n) time.
int rob(TreeNode root) {
int[] result = robHelper(root);
return Math.max(result[0], result[1]);
}
// result[0] = max if node NOT robbed, result[1] = max if node robbed
int[] robHelper(TreeNode node) {
if (node == null) return new int[]{0, 0};
int[] left = robHelper(node.left);
int[] right = robHelper(node.right);
int notRob = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
int rob = node.val + left[0] + right[0];
return new int[]{notRob, rob};
}Q29. How do you solve the N-th Tribonacci Number problem?
A: Tribonacci extends Fibonacci to three terms: T(n) = T(n-1) + T(n-2) + T(n-3), with base cases T(0)=0, T(1)=1, T(2)=1. It's solved identically to Fibonacci — either O(n) tabulation or O(1) space using three rolling variables instead of two — demonstrating that the "rolling variables" trick generalizes to any fixed-width recurrence window.
Q30. How do you solve Decode Ways (counting ways to decode a digit string into letters)?
A: Define dp[i] as the number of ways to decode the first i characters. A single-digit decode contributes dp[i-1] if that digit is 1-9 (not '0'), and a two-digit decode contributes dp[i-2] if the two-digit number formed is between 10 and 26. Summing the valid contributions gives the recurrence, computed in O(n) time and O(n) space (reducible to O(1)).
int numDecodings(String s) {
int n = s.length();
int[] dp = new int[n + 1];
dp[0] = 1;
dp[1] = s.charAt(0) == '0' ? 0 : 1;
for (int i = 2; i <= n; i++) {
int oneDigit = Integer.parseInt(s.substring(i - 1, i));
int twoDigit = Integer.parseInt(s.substring(i - 2, i));
if (oneDigit >= 1) dp[i] += dp[i - 1];
if (twoDigit >= 10 && twoDigit <= 26) dp[i] += dp[i - 2];
}
return dp[n];
}Q31. How do you solve Delete and Earn, and how does it reduce to House Robber?
A: First build a frequency-weighted "points per value" array: points[v] = v × count(v), since deleting all copies of one value earns that much and forces deletion of every copy of v-1 and v+1. That array is then exactly a House Robber instance — picking value v (all copies) forbids picking its immediate numeric neighbors v-1 and v+1 — solved with the same adjacent-exclusion DP.
Q32. How do you solve Perfect Squares (minimum number of perfect squares summing to n)?
A: Define dp[i] as the minimum count of perfect squares summing to i; for each i, try every perfect square j² <= i as the last term used, giving dp[i] = min(dp[i - j²] + 1) over all valid j. This is O(n√n) time overall since the inner loop only goes up to √i, and is structurally identical to unbounded coin-change with the "coins" being perfect squares.
int numSquares(int n) {
int[] dp = new int[n + 1];
Arrays.fill(dp, Integer.MAX_VALUE);
dp[0] = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j * j <= i; j++) {
dp[i] = Math.min(dp[i], dp[i - j * j] + 1);
}
}
return dp[n];
}Q33. How do you solve Jump Game (can you reach the last index)?
A: A DP formulation defines dp[i] as true if index i is reachable, set when some reachable earlier index j can jump at least to i, giving O(n²) time. The optimal approach is actually greedy, not DP: track the farthest reachable index while scanning left to right, and fail only if you reach a position beyond the current farthest reach, achieving O(n) time and O(1) space — a good example of when a DP-shaped problem has a simpler greedy solution.
Q34. How do you solve Jump Game II (minimum number of jumps to reach the last index)?
A: A DP formulation sets dp[i] to the minimum jumps to reach i, taking the minimum over all reachable predecessors plus one, which costs O(n²). The standard efficient solution uses a greedy "level order" expansion: track the current jump's farthest boundary and the farthest reachable index seen while scanning, incrementing the jump count each time you must cross the current boundary — O(n) time, O(1) space.
Q35. How do you solve the Paint Fence problem (count ways to paint posts with no more than two adjacent same-colored posts)?
A: Track two DP quantities per post: same[i] (ways where post i matches post i-1's color) and diff[i] (ways where it differs). A post can match the previous color only if the previous post differed from the one before it (same[i] = diff[i-1]), and can differ in (k-1) ways regardless (diff[i] = (same[i-1] + diff[i-1]) × (k-1)). The total is same[n-1] + diff[n-1], computed in O(n) time.
Q36. What is the general template for 1D DP problems?
A: Identify a single integer index (position, amount, or count) as the state; define dp[i] as the answer for that prefix or amount; express dp[i] in terms of a small fixed number of earlier entries (often dp[i-1] and/or dp[i-2], or a loop over all j < i); fill left to right after setting base cases at index 0 (and 1 if needed); and check whether the recurrence only needs a fixed window of recent entries to allow O(1) space optimization.
Q37. What defines a 2D DP problem, and how do you choose the two state dimensions?
A: A 2D DP problem needs two independent parameters to describe a subproblem — commonly a position in each of two sequences (LCS, edit distance), a position plus a remaining capacity/budget (knapsack), or a row and column in a grid (path-counting problems). The dimensions come directly from whatever varies independently across the recursive calls in the brute-force solution; if removing either parameter would make the subproblem ambiguous, it belongs in the state.
Q38. How do you solve Longest Common Subsequence (LCS)?
A: Define dp[i][j] as the LCS length of the first i characters of string a and first j characters of string b. If the characters match, extend the diagonal: dp[i][j] = dp[i-1][j-1] + 1; otherwise take the best of dropping a character from either string: dp[i][j] = max(dp[i-1][j], dp[i][j-1]). This runs in O(m×n) time and space.
int longestCommonSubsequence(String a, String b) {
int m = a.length(), n = b.length();
int[][] dp = new int[m + 1][n + 1];
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (a.charAt(i - 1) == b.charAt(j - 1)) dp[i][j] = dp[i - 1][j - 1] + 1;
else dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
}
}
return dp[m][n];
}Q39. How do you reconstruct the actual LCS string, not just its length?
A: After filling the DP table, walk backward from dp[m][n]: if the characters at the current i,j match, that character is part of the LCS — prepend it and move diagonally to (i-1, j-1); otherwise move toward whichever of dp[i-1][j] or dp[i][j-1] is larger (the direction that produced the current cell's value). This backtrack takes O(m+n) time but requires keeping the full table rather than a space-optimized rolling version.
Q40. How do you solve Edit Distance (Levenshtein distance)?
A: Define dp[i][j] as the minimum operations to convert the first i characters of a into the first j characters of b. If the current characters match, no operation is needed: dp[i][j] = dp[i-1][j-1]; otherwise take 1 plus the minimum of insert (dp[i][j-1]), delete (dp[i-1][j]), or replace (dp[i-1][j-1]). Base cases handle converting to/from an empty string via pure insertions or deletions. This is O(m×n) time and space.
int minDistance(String a, String b) {
int m = a.length(), n = b.length();
int[][] dp = new int[m + 1][n + 1];
for (int i = 0; i <= m; i++) dp[i][0] = i;
for (int j = 0; j <= n; j++) dp[0][j] = j;
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (a.charAt(i - 1) == b.charAt(j - 1)) dp[i][j] = dp[i - 1][j - 1];
else dp[i][j] = 1 + Math.min(dp[i - 1][j - 1], Math.min(dp[i - 1][j], dp[i][j - 1]));
}
}
return dp[m][n];
}Q41. How do you solve Longest Common Substring, and how does its DP transition differ from LCS?
A: Unlike LCS, a substring must be contiguous, so the moment characters mismatch the running match must reset to 0 rather than falling back to max(dp[i-1][j], dp[i][j-1]). Track a separate "best" variable across the whole fill, since the answer isn't necessarily at dp[m][n] — the longest run could end anywhere in the table.
int longestCommonSubstring(String a, String b) {
int m = a.length(), n = b.length(), best = 0;
int[][] dp = new int[m + 1][n + 1];
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (a.charAt(i - 1) == b.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1] + 1;
best = Math.max(best, dp[i][j]);
} // else dp[i][j] stays 0 -- must be contiguous
}
}
return best;
}Q42. How do you count Distinct Subsequences of one string that equal another?
A: Define dp[i][j] as the number of ways string s's first i characters can produce string t's first j characters as a subsequence. If the last characters match, you can either use that match (dp[i-1][j-1] ways) or skip s's character entirely (dp[i-1][j] ways), summing both; if they don't match, only skipping s's character is possible: dp[i][j] = dp[i-1][j]. Base case dp[i][0] = 1 (empty target is always achievable by deleting everything).
Q43. How do you solve Unique Paths in a grid (robot moving only right or down)?
A: Define dp[i][j] as the number of ways to reach cell (i, j); since the robot can only arrive from above or from the left, dp[i][j] = dp[i-1][j] + dp[i][j-1]. The entire first row and first column are seeded with 1 (only one way to travel in a straight line to reach them). This is O(m×n) time and space.
int uniquePaths(int m, int n) {
int[][] dp = new int[m][n];
for (int i = 0; i < m; i++) dp[i][0] = 1;
for (int j = 0; j < n; j++) dp[0][j] = 1;
for (int i = 1; i < m; i++)
for (int j = 1; j < n; j++)
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
return dp[m - 1][n - 1];
}Q44. How do you solve Unique Paths II with obstacles?
A: Identical recurrence to Unique Paths, except any cell containing an obstacle is forced to dp[i][j] = 0 (no path can pass through it), which also correctly zeroes out the first row/column past an obstacle since they'd otherwise inherit an invalid 1. Every other cell still sums contributions from above and the left, treating out-of-bounds neighbors as 0.
int uniquePathsWithObstacles(int[][] grid) {
int m = grid.length, n = grid[0].length;
int[][] dp = new int[m][n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 1) { dp[i][j] = 0; continue; }
if (i == 0 && j == 0) dp[i][j] = 1;
else dp[i][j] = (i > 0 ? dp[i - 1][j] : 0) + (j > 0 ? dp[i][j - 1] : 0);
}
}
return dp[m - 1][n - 1];
}Q45. How do you solve Minimum Path Sum in a grid?
A: Define dp[i][j] as the minimum cost to reach (i, j) from the top-left, which is the cell's own cost plus the cheaper of arriving from above or from the left: dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1]). The first row and column are seeded by accumulating along the single available direction, since they have only one possible incoming path.
int minPathSum(int[][] grid) {
int m = grid.length, n = grid[0].length;
int[][] dp = new int[m][n];
dp[0][0] = grid[0][0];
for (int i = 1; i < m; i++) dp[i][0] = dp[i - 1][0] + grid[i][0];
for (int j = 1; j < n; j++) dp[0][j] = dp[0][j - 1] + grid[0][j];
for (int i = 1; i < m; i++)
for (int j = 1; j < n; j++)
dp[i][j] = grid[i][j] + Math.min(dp[i - 1][j], dp[i][j - 1]);
return dp[m - 1][n - 1];
}Q46. How do you solve Minimum Falling Path Sum?
A: Starting from any cell in the first row, each move goes to the row below in the same column or a diagonally adjacent column, so dp[i][j] = grid[i][j] + min(dp[i-1][j-1], dp[i-1][j], dp[i-1][j+1]), treating out-of-bounds columns as infinity. The answer is the minimum value in the final row, computed in O(m×n) time.
Q47. How do you solve Interleaving String (checking if s3 is an interleaving of s1 and s2)?
A: Define dp[i][j] as true if the first i+j characters of s3 can be formed by interleaving the first i characters of s1 and first j characters of s2. dp[i][j] is true if either s1's i-th character matches the current s3 position and dp[i-1][j] is true, or s2's j-th character matches and dp[i][j-1] is true. This is O(m×n) time and space, and first requires m+n == s3.length() as a fast rejection.
boolean isInterleave(String s1, String s2, String s3) {
int m = s1.length(), n = s2.length();
if (m + n != s3.length()) return false;
boolean[][] dp = new boolean[m + 1][n + 1];
dp[0][0] = true;
for (int i = 1; i <= m; i++) dp[i][0] = dp[i - 1][0] && s1.charAt(i - 1) == s3.charAt(i - 1);
for (int j = 1; j <= n; j++) dp[0][j] = dp[0][j - 1] && s2.charAt(j - 1) == s3.charAt(j - 1);
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
dp[i][j] = (dp[i - 1][j] && s1.charAt(i - 1) == s3.charAt(i + j - 1))
|| (dp[i][j - 1] && s2.charAt(j - 1) == s3.charAt(i + j - 1));
}
}
return dp[m][n];
}Q48. How do you solve Maximal Square (largest square of 1s in a binary matrix)?
A: Define dp[i][j] as the side length of the largest all-1s square whose bottom-right corner is (i, j). If the cell is 1, the square can extend only as far as the smallest of the three neighboring squares (above, left, and diagonal above-left) allows: dp[i][j] = 1 + min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]). Track the maximum side seen and square it for the area. O(m×n) time and space.
int maximalSquare(char[][] matrix) {
int m = matrix.length, n = matrix[0].length, best = 0;
int[][] dp = new int[m + 1][n + 1];
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (matrix[i - 1][j - 1] == '1') {
dp[i][j] = 1 + Math.min(dp[i - 1][j - 1], Math.min(dp[i - 1][j], dp[i][j - 1]));
best = Math.max(best, dp[i][j]);
}
}
}
return best * best;
}Q49. How do you solve Longest Palindromic Subsequence?
A: The longest palindromic subsequence of s equals the LCS of s and its reverse — since any palindromic subsequence reads the same forward and backward, it must appear identically in both s and reverse(s). Alternatively, solve it directly with interval DP: dp[i][j] = dp[i+1][j-1] + 2 if s[i] == s[j], else max(dp[i+1][j], dp[i][j-1]), filled by increasing substring length.
Q50. How do you count all Palindromic Substrings in a string using DP?
A: Define dp[start][end] as true if the substring from start to end is a palindrome; it's true when the endpoints match and either the substring has length <=2 or the inner substring dp[start+1][end-1] is also a palindrome. Iterating end from left to right and start from 0 to end (so the shorter inner substrings are always finalized before longer outer ones) counts every true entry. O(n²) time and space.
int countSubstrings(String s) {
int n = s.length(), count = 0;
boolean[][] dp = new boolean[n][n];
for (int end = 0; end < n; end++) {
for (int start = 0; start <= end; start++) {
if (s.charAt(start) == s.charAt(end)
&& (end - start < 2 || dp[start + 1][end - 1])) {
dp[start][end] = true;
count++;
}
}
}
return count;
}Q51. How do you solve Regular Expression Matching with DP?
A: Define dp[i][j] as true if the first i characters of the text match the first j characters of the pattern. A literal character or '.' consumes one character from each and copies dp[i-1][j-1]; a '*' can either match zero occurrences of the preceding element (dp[i][j-2]) or, if the preceding element matches the current text character, extend a match by one (dp[i-1][j]). This is O(n×m) time and space, with '*' being the tricky two-way branch to get right.
Q52. How do you solve Wildcard Pattern Matching with DP?
A: Define dp[i][j] similarly to regex matching: '?' matches exactly one arbitrary character (dp[i][j] = dp[i-1][j-1]), while '*' matches any sequence including the empty one, so dp[i][j] = dp[i-1][j] || dp[i][j-1] — "consume one more text character under this star" or "treat the star as matching nothing." This is O(n×m) time and space, and simpler than regex matching since '*' here has no preceding-element dependency.
Q53. What is the general template for 2D DP problems on two strings?
A: Use dp[i][j] to represent a result involving the first i characters of string A and first j characters of string B; the transition almost always branches on whether A.charAt(i-1) == B.charAt(j-1), taking the diagonal dp[i-1][j-1] on a match and combining dp[i-1][j]/dp[i][j-1] otherwise. Base cases fill row 0 and column 0 (empty-string scenarios), and the table is filled row by row, left to right.
Q54. What is the general template for 2D DP problems on a grid?
A: Use dp[i][j] to represent the answer for reaching or ending at cell (i, j); the transition combines the values of whichever neighboring cells are valid "predecessors" under the allowed movement rules (typically above and left for right/down-only movement). Seed the first row and column based on the single reachable direction, then fill row by row, left to right, so every dependency is resolved before it's read.
Q55. What is the 0/1 Knapsack problem, and what is its recurrence relation?
A: Given items each with a weight and value, and a capacity limit, choose a subset (each item usable at most once) maximizing total value without exceeding capacity. The recurrence dp[i][w] = max(dp[i-1][w], dp[i-1][w - weight[i]] + value[i]) represents "skip item i" versus "take item i if it fits," where the second option must reference row i-1 (not row i) precisely because each item can only be used once.
Q56. How do you implement 0/1 Knapsack with a 2D DP table in Java?
A: Build a table of (n+1) rows by (capacity+1) columns; row i, column w holds the best value achievable using the first i items within capacity w. Each cell copies the "skip" option from the row above and, if the item fits, compares against the "take" option, which also reads from the row above at a reduced capacity. This is O(n×capacity) time and space.
int knapsack01(int[] weights, int[] values, int capacity) {
int n = weights.length;
int[][] dp = new int[n + 1][capacity + 1];
for (int i = 1; i <= n; i++) {
for (int w = 0; w <= capacity; w++) {
dp[i][w] = dp[i - 1][w]; // don't take item i
if (weights[i - 1] <= w) {
dp[i][w] = Math.max(dp[i][w], dp[i - 1][w - weights[i - 1]] + values[i - 1]);
}
}
}
return dp[n][capacity];
}Q57. How do you space-optimize 0/1 Knapsack to a 1D rolling array, and why must the capacity loop go right to left?
A: Since row i only ever depends on row i-1, a single 1D array of size (capacity+1) suffices if updated carefully. The capacity loop must run from high to low so that when computing dp[w], dp[w - weight] still holds the previous item's (row i-1) value rather than an already-updated value from the current item — going left to right would let one item be "taken" multiple times, turning it into unbounded knapsack by accident.
int knapsack01(int[] weights, int[] values, int capacity) {
int[] dp = new int[capacity + 1];
for (int i = 0; i < weights.length; i++) {
for (int w = capacity; w >= weights[i]; w--) { // right to left!
dp[w] = Math.max(dp[w], dp[w - weights[i]] + values[i]);
}
}
return dp[capacity];
}Q58. What is the Unbounded Knapsack problem, and how does its recurrence differ from 0/1 Knapsack?
A: Unbounded Knapsack allows each item type to be used an unlimited number of times, so the "take" transition reuses the same row rather than the previous one: dp[i][w] = max(dp[i-1][w], dp[i][w - weight[i]] + value[i]). That single change — reading dp[i] instead of dp[i-1] on the take branch — is what allows an item to be selected repeatedly.
Q59. How do you implement Unbounded Knapsack in Java, and why does its capacity loop go left to right?
A: With a 1D rolling array, the capacity loop runs ascending (low to high) precisely because you want dp[w - weight[i]] to already reflect this item potentially having been used to reach the smaller capacity — enabling reuse. This is the mirror image of the 0/1 knapsack rule, where the descending loop deliberately prevents that reuse.
int unboundedKnapsack(int[] weights, int[] values, int capacity) {
int[] dp = new int[capacity + 1];
for (int w = 1; w <= capacity; w++) { // left to right -- reuse allowed
for (int i = 0; i < weights.length; i++) {
if (weights[i] <= w) {
dp[w] = Math.max(dp[w], dp[w - weights[i]] + values[i]);
}
}
}
return dp[capacity];
}Q60. How do you solve Coin Change (minimum number of coins to make an amount)?
A: This is unbounded knapsack in disguise: dp[a] is the fewest coins summing to amount a, computed as 1 + min(dp[a - coin]) over every coin that fits. Initialize dp[0] = 0 and all other entries to a sentinel larger than any valid answer (like amount+1), returning -1 if the final entry never improved from that sentinel. O(amount × numCoins) time.
int coinChange(int[] coins, int amount) {
int[] dp = new int[amount + 1];
Arrays.fill(dp, amount + 1);
dp[0] = 0;
for (int a = 1; a <= amount; a++) {
for (int coin : coins) {
if (coin <= a) dp[a] = Math.min(dp[a], dp[a - coin] + 1);
}
}
return dp[amount] > amount ? -1 : dp[amount];
}Q61. How do you solve Coin Change II (number of distinct ways to make an amount)?
A: Define dp[a] as the number of ways to make amount a; unlike counting problems in general, this must iterate coins in the outer loop and amounts in the inner loop to count combinations (unordered selections), not permutations. Each coin, once processed, contributes its ways to every amount it can help build, accumulating dp[a] += dp[a - coin].
int change(int amount, int[] coins) {
int[] dp = new int[amount + 1];
dp[0] = 1;
for (int coin : coins) { // coin outer loop -> combinations
for (int a = coin; a <= amount; a++) {
dp[a] += dp[a - coin];
}
}
return dp[amount];
}Q62. Why does swapping the loop order in Coin Change II change the answer from combinations to permutations?
A: With coin as the outer loop, each coin type is "committed" to before moving to the next, so a sequence like (1,2) and (2,1) are never double-counted — only combinations are counted. If amount is the outer loop instead (coin inner), every ordering of the same coin multiset is counted separately as a distinct sequence, because at each amount all coins are considered fresh regardless of what order previous amounts used them in — turning the count into permutations, which is the exact recurrence used for Combination Sum IV.
Q63. How do you solve the Subset Sum problem (can a subset sum to a target)?
A: Use a boolean 1D DP array where dp[s] means sum s is achievable; for each number, update reachable sums by iterating the target loop from high to low (0/1 usage per number, same rule as 0/1 knapsack) so a number isn't reused within the same pass. O(n × target) time, O(target) space.
boolean canReachSum(int[] nums, int target) {
boolean[] dp = new boolean[target + 1];
dp[0] = true;
for (int num : nums) {
for (int s = target; s >= num; s--) { // right to left -- each num used once
dp[s] = dp[s] || dp[s - num];
}
}
return dp[target];
}Q64. How do you solve Partition Equal Subset Sum, and how does it reduce to Subset Sum?
A: If the total array sum is odd, an equal partition is impossible immediately. Otherwise, the question becomes exactly Subset Sum with target = totalSum / 2 — if any subset can reach half the total, the remaining elements automatically sum to the other half, giving a valid two-way partition.
Q65. How do you solve Target Sum (assign + or - signs to reach a target), and how does it reduce to Subset Sum?
A: Split the array conceptually into a "positive" subset P and "negative" subset N; the target constraint sum(P) - sum(N) = target combined with sum(P) + sum(N) = totalSum algebraically gives sum(P) = (totalSum + target) / 2. So the problem reduces to counting subsets that sum to that fixed value — the same subset-sum DP, but counting ways (dp[s] += dp[s - num]) instead of a boolean reachability check.
Q66. How do you solve the Rod Cutting problem?
A: Define dp[len] as the maximum revenue obtainable from a rod of length len; try every possible first cut length c from 1 to len, and take dp[len] = max(price[c] + dp[len - c]) over all c. This is unbounded-knapsack-shaped since the same cut length can be reused any number of times, giving O(n²) time.
int rodCutting(int[] price, int n) {
int[] dp = new int[n + 1];
for (int len = 1; len <= n; len++) {
for (int cut = 1; cut <= len; cut++) {
dp[len] = Math.max(dp[len], price[cut - 1] + dp[len - cut]);
}
}
return dp[n];
}Q67. Why is Fractional Knapsack solved greedily instead of with DP?
A: Because items can be split into arbitrary fractions, always taking as much as possible of the item with the highest value-to-weight ratio first is provably optimal — there's no scenario where a locally worse ratio choice leads to a better global outcome, since any leftover capacity can always be filled with a fraction of the next-best item. That greedy-choice property doesn't hold for 0/1 knapsack, where items are indivisible and a greedy ratio-based pick can leave capacity stranded, forcing the full DP exploration of subset choices.
Q68. What is the difference between 0/1 Knapsack, Unbounded Knapsack, and Fractional Knapsack?
A: 0/1 Knapsack: each item usable at most once, solved with DP (greedy fails). Unbounded Knapsack: each item type usable unlimited times, also solved with DP but with a reworked recurrence allowing reuse. Fractional Knapsack: items can be split into any fraction, solved optimally and efficiently with a greedy value-to-weight ratio approach, no DP required at all.
Q69. How do you solve Longest Increasing Subsequence with an O(n²) DP approach?
A: Define dp[i] as the length of the longest increasing subsequence ending exactly at index i. For each i, scan all earlier indices j; if nums[j] < nums[i], the subsequence ending at j can be extended: dp[i] = max(dp[i], dp[j] + 1). Every dp[i] starts at 1 (the element alone), and the answer is the maximum value across the whole array.
int lengthOfLIS(int[] nums) {
int n = nums.length;
int[] dp = new int[n];
Arrays.fill(dp, 1);
int best = 1;
for (int i = 1; i < n; i++) {
for (int j = 0; j < i; j++) {
if (nums[j] < nums[i]) dp[i] = Math.max(dp[i], dp[j] + 1);
}
best = Math.max(best, dp[i]);
}
return best;
}Q70. How do you solve Longest Increasing Subsequence in O(n log n) using patience sorting / binary search?
A: Maintain an array "tails" where tails[k] holds the smallest possible tail value of any increasing subsequence of length k+1 found so far. For each new number, binary search for its insertion position in tails (the first tail >= it) and overwrite that slot, or append if it's larger than all tails. The final size of tails is the LIS length — this doesn't reconstruct a valid subsequence directly, but the length is always correct.
int lengthOfLIS(int[] nums) {
int[] tails = new int[nums.length];
int size = 0;
for (int num : nums) {
int lo = 0, hi = size;
while (lo < hi) {
int mid = (lo + hi) / 2;
if (tails[mid] < num) lo = mid + 1; else hi = mid;
}
tails[lo] = num;
if (lo == size) size++;
}
return size;
}Q71. How do you reconstruct the actual LIS sequence, not just its length?
A: With the O(n²) DP approach, also store a "predecessor" index for each i whenever dp[i] is updated from dp[j]; after filling the table, find the index with the maximum dp value and follow predecessor links backward to reconstruct the full subsequence. The O(n log n) patience-sorting approach can also reconstruct it by additionally storing, for each element, which "pile" it landed on and a backpointer to the top of the previous pile at insertion time.
Q72. How do you solve the Longest Bitonic Subsequence problem (increases then decreases)?
A: Compute two arrays with the standard LIS DP: inc[i], the longest increasing subsequence ending at i (scanning left to right), and dec[i], the longest decreasing subsequence starting at i (scanning right to left, or equivalently LIS on the reversed array). The longest bitonic subsequence through index i is inc[i] + dec[i] - 1 (i is counted in both), and the answer is the max over all i. O(n²) time.
Q73. How do you count the Number of Longest Increasing Subsequences?
A: Alongside dp[i] (LIS length ending at i), maintain count[i] (number of LIS of that length ending at i). When extending from j to i with nums[j] < nums[i]: if dp[j] + 1 > dp[i], a strictly longer subsequence was found, so reset count[i] = count[j]; if equal, another way to achieve the same best length was found, so count[i] += count[j]. Sum count[i] over all i achieving the global maximum length.
Q74. How do you solve Russian Doll Envelopes (2D LIS)?
A: Sort envelopes by width ascending, but for equal widths sort height descending (to prevent same-width envelopes from being counted as nestable within each other in the same pass). Then the answer is simply the LIS of the height sequence, solvable in O(n log n) with the patience-sorting technique — reducing a 2D nesting problem to a 1D LIS problem via a clever sort order.
Q75. How do you solve Maximum Sum Increasing Subsequence?
A: Nearly identical to standard LIS DP, but track sum instead of length: dp[i] is the maximum sum of an increasing subsequence ending at i, seeded with nums[i] itself, and updated as dp[i] = max(dp[i], dp[j] + nums[i]) for every j < i with nums[j] < nums[i]. O(n²) time, same structure as LIS with a different "combine" operation.
Q76. How do you solve the Longest Chain of Pairs problem?
A: Sort pairs by their first element, then it becomes LIS-shaped: dp[i] is the longest chain ending with pair i, extended from any earlier pair j whose second element is less than pair i's first element (pairs[j][1] < pairs[i][0]). This is O(n²) with the DP approach, or O(n log n) with a greedy approach that sorts by the second element and always extends the chain with the smallest available "end" value.
Q77. How do you solve the Box Stacking problem, and how does it reduce to LIS?
A: First generate all rotations of every box (each box can be oriented three ways, giving a base width×depth and a height), then sort these by base area descending. The problem becomes a variant of LIS on height: dp[i] is the max stack height ending with box i, extended from any earlier box j whose base strictly contains box i's base in both dimensions. This is O(n²) after the O(n log n) sort.
Q78. How do you find the Minimum Number of Deletions to make an array sorted (non-decreasing)?
A: The elements you keep must form a non-decreasing subsequence, so the minimum deletions is n - LIS(array) where LIS is computed allowing equal adjacent values (a "longest non-decreasing subsequence" variant). Maximizing the kept subsequence directly minimizes what must be removed, so any LIS algorithm (O(n²) or O(n log n)) applies with a small tweak to the comparison operator.
Q79. What is the Matrix Chain Multiplication problem, and why does multiplication order matter?
A: Given a chain of matrices to multiply, the problem asks for the parenthesization (grouping order) that minimizes the total number of scalar multiplications — matrix multiplication is associative (the final result is the same regardless of order) but not equally costly for every grouping. For example, multiplying a 10×100, 100×5, and 5×50 chain costs vastly different totals depending on which pair is multiplied first, even though associativity guarantees the same final matrix.
Q80. How do you implement Matrix Chain Multiplication with interval DP in Java?
A: Define dp[i][j] as the minimum cost to multiply matrices i through j; try every split point k between i and j, combining the cost of the left sub-chain, the right sub-chain, and the cost of multiplying the two resulting matrices together (dims[i-1] × dims[k] × dims[j]). Iterate by increasing chain length so shorter sub-chains are always finalized before longer ones need them.
int matrixChainOrder(int[] dims) {
int n = dims.length - 1; // number of matrices
int[][] dp = new int[n + 1][n + 1];
for (int len = 2; len <= n; len++) {
for (int i = 1; i <= n - len + 1; i++) {
int j = i + len - 1;
dp[i][j] = Integer.MAX_VALUE;
for (int k = i; k < j; k++) {
int cost = dp[i][k] + dp[k + 1][j] + dims[i - 1] * dims[k] * dims[j];
dp[i][j] = Math.min(dp[i][j], cost);
}
}
}
return dp[1][n];
}Q81. Why is Matrix Chain Multiplication O(n³) time and O(n²) space?
A: There are O(n²) distinct (i, j) subchain states, and computing each one requires trying up to O(n) possible split points k, giving O(n²) × O(n) = O(n³) total time. The space is O(n²) simply to store the answer for every (i, j) pair in the table, which cannot easily be compressed since longer-chain answers depend on many different shorter-chain answers spread throughout the table, not just an adjacent row.
Q82. How do you solve Palindrome Partitioning II (minimum cuts to partition a string into palindromes)?
A: First precompute an O(n²) table marking every substring as palindrome or not (via interval DP, expanding from shorter to longer substrings). Then define dp[i] as the minimum cuts needed for the prefix ending at i: if the whole prefix is itself a palindrome, zero cuts are needed; otherwise try every earlier cut point j and take dp[i] = min(dp[j-1] + 1) for every j where the substring from j to i is a palindrome.
int minCut(String s) {
int n = s.length();
boolean[][] isPalin = new boolean[n][n];
for (int end = 0; end < n; end++)
for (int start = 0; start <= end; start++)
if (s.charAt(start) == s.charAt(end) && (end - start < 2 || isPalin[start + 1][end - 1]))
isPalin[start][end] = true;
int[] dp = new int[n];
for (int i = 0; i < n; i++) {
if (isPalin[0][i]) { dp[i] = 0; continue; }
dp[i] = Integer.MAX_VALUE;
for (int j = 1; j <= i; j++) {
if (isPalin[j][i]) dp[i] = Math.min(dp[i], dp[j - 1] + 1);
}
}
return dp[n - 1];
}Q83. How do you precompute a palindrome table to speed up Palindrome Partitioning?
A: Fill a boolean table by increasing substring length: single characters and empty ranges are trivially palindromes; a substring of length >= 2 is a palindrome only if its endpoints match and the substring strictly inside it (already computed, being shorter) is also a palindrome. This precomputation is O(n²) and turns every subsequent "is this substring a palindrome?" query into an O(1) lookup instead of an O(n) re-check.
Q84. How do you solve Burst Balloons with interval DP?
A: Pad the array with virtual 1s at both ends, then define dp[i][j] as the maximum coins obtainable from bursting all balloons strictly between i and j. The key insight is to think about which balloon is burst last within that range (not first) — for each candidate "last balloon" k, the coins gained are nums[i] × nums[k] × nums[j] plus the best result of the two now-independent sub-ranges, since only the boundary balloons matter once everything inside has already been cleared. O(n³) time.
Q85. How do you solve the Egg Drop Puzzle with DP?
A: Define dp[e][f] as the minimum worst-case trials needed with e eggs and f floors. Dropping from a chosen floor either breaks the egg (reducing to dp[e-1][f-1], checking floors below) or doesn't (reducing to dp[e][f-1], checking floors above); you take 1 plus the worse of the two outcomes, then minimize over every possible floor choice. The naive version is O(e×f²) due to trying every floor per state; it can be optimized to O(e×f) using binary search on the monotonic trial count, or reformulated in terms of "max floors coverable" for O(e×f) directly.
Q86. How do you solve Boolean Parenthesization (count ways to parenthesize a boolean expression to evaluate to True)?
A: Use interval DP with two tables, trueCount[i][j] and falseCount[i][j], for the substring of operands/operators from i to j. For every split point k (an operator position), combine the true/false counts of the left and right sub-expressions according to that operator's truth table (AND, OR, XOR), summing all ways that yield True (or False) across every valid split. O(n³) time, structurally identical to matrix chain multiplication's interval-splitting pattern.
Q87. What is the general template for interval DP problems?
A: Define dp[i][j] as the answer for the subrange/sub-chain from i to j; the transition tries every possible split or "last operation" point k between i and j, combining the pre-computed answers for the two resulting sub-intervals plus some cost/value tied to the split itself. Crucially, the table must be filled by increasing interval length (not by raw row/column index), since a length-L interval's answer depends on shorter sub-intervals nested inside it.
Q88. How does DP work on trees, and what's the typical state definition?
A: Tree DP computes, for each node, one or more values that summarize the best/aggregate result of the subtree rooted there, using a post-order traversal so every child's values are ready before the parent needs them. The state often needs more than one value per node — for example "best result if this node is included" and "best result if it's excluded" — because a node's own optimal choice can depend on constraints its children impose (like the adjacency exclusion in House Robber III).
Q89. How do you compute the Diameter of a Binary Tree using a DP-style post-order traversal?
A: The diameter (longest path between any two nodes, not necessarily through the root) at each node is the sum of the left and right subtree depths, since the longest path through that node passes down both sides. A single post-order traversal computes each node's depth while simultaneously updating a global "best diameter seen" using the current node's left-depth + right-depth, giving O(n) time overall instead of the O(n²) naive approach of recomputing depth from every node.
int diameter = 0;
int diameterOfBinaryTree(TreeNode root) {
depth(root);
return diameter;
}
int depth(TreeNode node) {
if (node == null) return 0;
int left = depth(node.left);
int right = depth(node.right);
diameter = Math.max(diameter, left + right);
return 1 + Math.max(left, right);
}Q90. How do you find the Maximum Path Sum in a Binary Tree using DP?
A: For each node in post-order, compute the best "downward" contribution it can offer to a parent — its own value plus the larger of its children's positive contributions (negative contributions are clamped to 0, since including a negative branch would only hurt). Separately, at each node, evaluate the best "through this node" path (node value plus both children's positive contributions) and update a global maximum, since that "through" path can never be extended further up to a parent.
Q91. How do you compute the Longest Path in a Directed Acyclic Graph (DAG) using DP and topological sort?
A: Because a DAG has no cycles, processing nodes in topological order guarantees that every predecessor of a node is finalized before the node itself is relaxed. Define dp[v] as the longest path ending at v; while processing nodes in topological order, relax each outgoing edge (u, v) as dp[v] = max(dp[v], dp[u] + weight). This is O(V + E) time, essentially DP layered on top of a topological traversal instead of a simple array index.
int longestPathDAG(int n, List<int[]>[] adj) {
int[] indegree = new int[n];
for (List<int[]> edges : adj)
for (int[] e : edges) indegree[e[0]]++;
Deque<Integer> queue = new ArrayDeque<>();
int[] dp = new int[n];
for (int i = 0; i < n; i++) if (indegree[i] == 0) queue.add(i);
while (!queue.isEmpty()) {
int u = queue.poll();
for (int[] e : adj[u]) {
int v = e[0], weight = e[1];
dp[v] = Math.max(dp[v], dp[u] + weight);
if (--indegree[v] == 0) queue.add(v);
}
}
return Arrays.stream(dp).max().getAsInt();
}Q92. How do you count the Number of Distinct Paths between two nodes in a DAG using DP?
A: Define dp[v] as the number of distinct paths from the source to node v; process nodes in topological order and, for each edge (u, v), accumulate dp[v] += dp[u], since every path reaching u can be extended by that edge to reach v. Seed dp[source] = 1, and the final answer is dp[destination], computed in O(V + E) time.
Q93. What is bitmask DP, and how does it represent subsets as state?
A: Bitmask DP encodes a subset of up to ~20 elements as an integer, where bit k being set means element k is included in the subset — this lets a subset be used directly as an array index (state) rather than needing a hash set or complex key. It's the standard way to add "which items have I already used/visited" as part of the DP state for problems like TSP or assignment problems, at the cost of O(2ⁿ) states, which is why it's only practical for small n (typically n <= 20-22).
Q94. How do you solve the Traveling Salesman Problem (TSP) using bitmask DP?
A: Define dp[mask][u] as the minimum cost of a path that has visited exactly the cities in mask, currently ending at city u. Starting from dp[{0}][0] = 0, transition by trying to extend the path to any unvisited city v: dp[mask | (1<<v)][v] = min(..., dp[mask][u] + dist[u][v]). The final answer closes the tour by adding the return edge to the start city over all possible ending cities. This is O(2ⁿ × n²) time, exponential but far better than O(n!) brute-force permutations.
int tsp(int[][] dist) {
int n = dist.length;
int[][] dp = new int[1 << n][n];
for (int[] row : dp) Arrays.fill(row, Integer.MAX_VALUE / 2);
dp[1][0] = 0; // start at city 0, only city 0 visited
for (int mask = 1; mask < (1 << n); mask++) {
for (int u = 0; u < n; u++) {
if ((mask & (1 << u)) == 0 || dp[mask][u] == Integer.MAX_VALUE / 2) continue;
for (int v = 0; v < n; v++) {
if ((mask & (1 << v)) != 0) continue;
int next = mask | (1 << v);
dp[next][v] = Math.min(dp[next][v], dp[mask][u] + dist[u][v]);
}
}
}
int full = (1 << n) - 1, best = Integer.MAX_VALUE;
for (int u = 1; u < n; u++) best = Math.min(best, dp[full][u] + dist[u][0]);
return best;
}Q95. Why must DP on a general graph with cycles use topological order or explicit memoization rather than naive tabulation?
A: Naive tabulation assumes a fixed iteration order (like increasing index) guarantees every dependency is already computed — that assumption breaks on a cyclic graph, since there's no consistent linear order where every predecessor precedes every successor. Top-down memoization sidesteps this by computing values on demand via recursion, using a "currently visiting" marker to detect and reject cycles (since a DP state genuinely can't depend on itself in a well-formed problem); a DAG's topological order is really just a way to get tabulation's iteration order right without recursion.
Q96. How does DP relate to the Bellman-Ford shortest path algorithm?
A: Bellman-Ford is fundamentally a DP over "number of edges used": dp[k][v] is the shortest distance to v using at most k edges, relaxing dp[k][v] = min(dp[k-1][v], dp[k-1][u] + weight(u,v)) for every edge, iterated for up to V-1 rounds (since a shortest simple path has at most V-1 edges). This DP framing is exactly why Bellman-Ford correctly handles negative edge weights and can detect negative cycles (a V-th round that still finds improvements), unlike Dijkstra's greedy approach.
Q97. What is the rolling array technique, and why does it work?
A: The rolling array technique keeps only the small number of previous rows (or columns) that the current row's transition actually reads from — often just one — instead of the entire table, since older rows are never referenced again once the current row is complete. It works whenever the recurrence has a bounded "lookback" (like i-1 only, not an arbitrary earlier i), which is common in 1D-window recurrences and grid-style 2D DPs.
Q98. How do you convert a 2D DP table to a 1D rolling array in Java?
A: Replace the two-dimensional table with two 1D arrays representing "previous row" and "current row," computing the current row entirely from the previous one, then swapping references (or copying) before moving to the next row. This reduces space from O(m×n) to O(n) while keeping the exact same time complexity, at the cost of losing the ability to backtrack through the full history for path reconstruction.
int lcsSpaceOptimized(String a, String b) {
int m = a.length(), n = b.length();
int[] prev = new int[n + 1], curr = new int[n + 1];
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (a.charAt(i - 1) == b.charAt(j - 1)) curr[j] = prev[j - 1] + 1;
else curr[j] = Math.max(prev[j], curr[j - 1]);
}
int[] temp = prev; prev = curr; curr = temp;
}
return prev[n];
}Q99. When can you NOT safely apply rolling-array space optimization?
A: You can't roll the array away when you need to reconstruct the actual optimal solution (not just its value), since backtracking requires the full history of every row; you also can't roll it when the recurrence genuinely depends on a state more than one or two steps back (like referencing dp[i-3] as well as dp[i-1]) unless you keep exactly that many rows in a small circular buffer instead of just one.
Q100. How do you reduce a 3D DP problem to 2D space?
A: If the third dimension's recurrence only depends on the immediately preceding value along that dimension (analogous to the 2D-to-1D rolling row trick), you can drop that dimension to two alternating 2D "layers," computing the current layer entirely from the previous one. This is common in problems layering an extra dimension like "number of moves used so far" or "number of transactions completed" on top of an already-2D state.
Q101. What is the general trade-off of space optimization in DP (time vs space vs reconstructability)?
A: Space optimization (rolling arrays, dropping dimensions) never changes the time complexity — you still visit every state exactly once — but it reduces memory from the full table size down to whatever the recurrence's lookback window requires. The cost is losing direct access to earlier rows/layers, which means you sacrifice the ability to backtrack and reconstruct the actual optimal sequence of choices unless you separately store extra bookkeeping (like parent pointers) alongside the optimized table.
Q102. How can bitmasking itself be viewed as a space-optimization technique for subset-based DP?
A: Representing a subset as a single integer bitmask (instead of, say, a HashSet or boolean array per state) compresses what would otherwise be an expensive-to-hash or high-overhead object into one machine word that can be used directly as an array index. This turns subset membership checks and unions/intersections into O(1) bitwise operations, and lets the DP table itself be a flat array indexed by mask rather than a map keyed by set contents — both a space and a constant-factor time win.
Q103. What's the difference between using a HashMap and a plain array for memoization in Java, and when would you choose each?
A: An array gives O(1) true constant-time access with no hashing overhead, but requires the state to map cleanly to small, bounded, non-negative integer indices (or a manually computed composite index for multi-dimensional state). A HashMap handles arbitrary or sparse state spaces (like a state that's a String, a List, or negative/huge numbers) at the cost of hashing overhead and boxing — use an array whenever the state space is small and dense, and a HashMap when it isn't.
Q104. Why can top-down memoized recursion cause a StackOverflowError in Java that a bottom-up solution avoids?
A: Each recursive call consumes a stack frame, and Java's default thread stack size (commonly around 512KB-1MB) can only hold a few thousand to tens of thousands of frames depending on frame size — a DP problem with a linear chain of ~100,000+ dependent states (like Fibonacci of a huge n, or a long string DP) can exceed that limit purely from recursion depth, regardless of how fast each individual call is. Bottom-up tabulation uses an explicit loop instead of the call stack, so its "depth" only costs heap memory for the table, not stack frames.
Q105. How do you convert a recursive memoized DP solution into an iterative one to avoid recursion-depth issues?
A: Identify the state's dependency order from the recurrence (which states must be finalized before a given state can be computed), then rewrite the recursion as nested loops that iterate in exactly that order, reading from and writing to the same-shaped table the memoization would have used. In practice this simply means translating "top-down with a cache" into "bottom-up with the same cache, filled iteratively" — the recurrence relation itself doesn't change, only how it's driven.
Q106. What are the most common bugs when implementing DP solutions?
A: The most frequent bugs are: uninitialized or incorrect base cases (especially row/column 0 in 2D DP), off-by-one errors when mapping 1-indexed DP arrays to 0-indexed input arrays, filling the table in the wrong order so a transition reads an unfilled cell (often silently returning 0 instead of erroring), and reusing a rolling array incorrectly (iterating the wrong direction, causing an item to be "used twice" as in 0/1 vs unbounded knapsack). Careful base-case enumeration and dependency-order verification catch most of these before they cause wrong answers.
Q107. How do you debug a DP solution that gives the wrong answer?
A: Print or step through the full DP table for a small hand-traceable input and compare each cell against manual computation, since the wrong value usually appears early and propagates — the first incorrect cell pinpoints exactly where the recurrence or base case is wrong. Also double-check the fill order (are dependencies computed before they're read?), the loop bounds (off-by-one at the boundaries), and, for rolling-array versions, temporarily switch back to a full 2D table to rule out a space-optimization bug before hunting for a logic bug.
Q108. How do you solve Word Break (can a string be segmented into dictionary words)?
A: Define dp[i] as true if the prefix of length i can be segmented using dictionary words. For each i, check every earlier split point j: if dp[j] is true and the substring from j to i is in the dictionary, then dp[i] is true. Using a HashSet for O(1) dictionary lookups, this runs in O(n²) time (n² substring checks, each O(1) after using a set) plus substring extraction cost.
boolean wordBreak(String s, List<String> wordDict) {
Set<String> dict = new HashSet<>(wordDict);
boolean[] dp = new boolean[s.length() + 1];
dp[0] = true;
for (int i = 1; i <= s.length(); i++) {
for (int j = 0; j < i; j++) {
if (dp[j] && dict.contains(s.substring(j, i))) { dp[i] = true; break; }
}
}
return dp[s.length()];
}Q109. How do you solve Combination Sum IV (count ordered ways to reach a target, i.e. permutations)?
A: Define dp[t] as the number of ordered sequences of numbers summing to t; unlike Coin Change II, the target is the outer loop and every number is tried inside it at every target, so different orderings of the same numbers are counted separately (matching "combination sum IV" being a permutation count despite its name). dp[0] = 1 (the empty sequence), and dp[t] = sum(dp[t - num]) over every usable num <= t.
int combinationSum4(int[] nums, int target) {
int[] dp = new int[target + 1];
dp[0] = 1;
for (int t = 1; t <= target; t++) {
for (int num : nums) {
if (num <= t) dp[t] += dp[t - num];
}
}
return dp[target];
}Q110. How do you solve Best Time to Buy and Sell Stock with Cooldown using state-machine DP?
A: Model three states per day: holding a stock, having just sold (entering cooldown), and resting (not holding, not in cooldown). Transition each day: "hold" can extend from yesterday's hold or newly buy from yesterday's rest; "sold" can only come from yesterday's hold plus today's sale price; "rest" carries over from yesterday's rest or yesterday's sold (cooldown finished). Tracking three rolling variables gives O(n) time, O(1) space.
int maxProfit(int[] prices) {
int hold = Integer.MIN_VALUE, sold = 0, rest = 0;
for (int price : prices) {
int prevSold = sold;
sold = hold + price;
hold = Math.max(hold, rest - price);
rest = Math.max(rest, prevSold);
}
return Math.max(sold, rest);
}Q111. What is "state machine DP," and how does it generalize the stock buy/sell problems?
A: State machine DP models a problem as a small set of named states (like "holding," "sold," "resting," or "k transactions used") with explicit legal transitions between them each step, tracking the best achievable value for each state independently rather than one single scalar DP value per index. It generalizes cleanly across the whole family of stock problems — unlimited transactions, at most k transactions, with cooldown, with transaction fees — by simply adding or adjusting states and their transition rules, rather than inventing a new recurrence from scratch each time.
Q112. What are the most commonly asked DP interview problems at companies like Amazon, Google, Microsoft, Infosys, and TCS in 2026?
A: Across FAANG-style interviews, the recurring favorites are Longest Common Subsequence, Edit Distance, 0/1 Knapsack and Coin Change, House Robber (all variants), Longest Increasing Subsequence, Unique Paths, Word Break, and the stock buy/sell family — problems chosen because they each showcase a distinct DP pattern (string DP, knapsack DP, grid DP, sequence DP, state-machine DP) rather than being one-off puzzles. Indian service-based interviewers (Infosys, TCS) tend to emphasize the foundational 1D/2D patterns and clear Java implementation, while product companies (Amazon, Google, Microsoft) more often probe space optimization, edge cases, and the reasoning behind why a greedy approach fails where DP succeeds.
Post a Comment
Add