Interval DP Interview Questions
Last updated 2026-11-19
Interval dynamic programming solves a problem on a range by combining answers for smaller ranges inside it. The state is a pair of endpoints (i, j), and the transition usually splits the interval at some point k. It is the family behind matrix chain multiplication, burst balloons and many game and palindrome problems.
This page walks through ten problems, each with Python and Java code, complexity and edge cases. Basic DP technique is in dynamic programming interview questions, and the related string versions are in longest common subsequence interview questions. Divide and conquer style splitting is in divide and conquer interview questions.
| State | dp[i][j] for interval i to j |
|---|---|
| Order | Increasing interval length |
| Typical cost | O(n^3), or O(n^2) when no split is searched |
| Key idea | Choose a split, often the last action |
The pattern and when to spot it
Interval DP appears when operations act on a contiguous range and the result depends on how the range is divided: parenthesising a product, cutting a stick, bursting balloons, merging adjacent piles, or playing from both ends of an array. If removing or merging an element changes who is adjacent to whom, the subproblems become tangled unless you reverse the viewpoint.
The central trick is to pick the last operation in the interval rather than the first. In burst balloons the last balloon to burst has fixed neighbours at the interval ends, so the left and right parts are independent. The same idea fits cutting a stick. Fill the table by increasing length so every smaller interval is ready. Problems where only the ends matter, such as palindromes and coin games, have O(1) transitions and run in O(n^2).
Common mistakes
- Iterating i and j in an order where dp[i+1][j-1] or dp[k][j] is not yet computed.
- Choosing the first operation instead of the last, which leaves subproblems dependent.
- Forgetting to pad boundary values, such as the extra ones in burst balloons.
- Reading dp[i+1][j-1] when the interval has length 2, where the inner interval is empty.
- Overflowing int in cost products for large inputs.
Interval DP Interview Questions: questions with worked answers
1 Longest palindromic subsequence with an interval table
mediumLet dp[i][j] be the longest palindromic subsequence inside s[i..j]. If the ends match, it is dp[i+1][j-1] + 2. Otherwise drop one end: max(dp[i+1][j], dp[i][j-1]). Single characters are 1. Fill by increasing interval length, or equivalently with i descending and j ascending so the needed cells already exist. Time O(n^2), space O(n^2). Edge cases: empty string, single character, all identical (n), adjacent equal pair where dp[i+1][j-1] refers to an empty interval (0).
pythondef lps(s): n = len(s) if n == 0: return 0 dp = [[0] * n for _ in range(n)] for i in range(n - 1, -1, -1): dp[i][i] = 1 for j in range(i + 1, n): if s[i] == s[j]: dp[i][j] = (dp[i + 1][j - 1] if i + 1 <= j - 1 else 0) + 2 else: dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]) return dp[0][n - 1]javaint lps(String s) { int n = s.length(); if (n == 0) return 0; int[][] dp = new int[n][n]; for (int i = n - 1; i >= 0; i--) { dp[i][i] = 1; for (int j = i + 1; j < n; j++) { if (s.charAt(i) == s.charAt(j)) dp[i][j] = (i + 1 <= j - 1 ? dp[i + 1][j - 1] : 0) + 2; else dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]); } } return dp[0][n - 1]; }2 Minimum insertions to make a string a palindrome (interval form)
mediumdp[i][j] is the fewest insertions to make s[i..j] a palindrome. If the ends match, it equals dp[i+1][j-1]. Otherwise insert a copy of one end, so 1 + min(dp[i+1][j], dp[i][j-1]). Empty and single-character intervals need none. Time O(n^2), space O(n^2). Edge cases: already a palindrome (0), two different letters (1), empty string, reading dp[i+1][j-1] for adjacent indexes (0).
pythondef min_insertions(s): n = len(s) dp = [[0] * n for _ in range(n)] for length in range(2, n + 1): for i in range(n - length + 1): j = i + length - 1 if s[i] == s[j]: dp[i][j] = dp[i + 1][j - 1] if length > 2 else 0 else: dp[i][j] = 1 + min(dp[i + 1][j], dp[i][j - 1]) return dp[0][n - 1] if n else 0javaint minInsertions(String s) { int n = s.length(); int[][] dp = new int[n][n]; for (int len = 2; len <= n; len++) for (int i = 0; i + len - 1 < n; i++) { int j = i + len - 1; if (s.charAt(i) == s.charAt(j)) dp[i][j] = len > 2 ? dp[i + 1][j - 1] : 0; else dp[i][j] = 1 + Math.min(dp[i + 1][j], dp[i][j - 1]); } return n == 0 ? 0 : dp[0][n - 1]; }3 Predict the winner of a two-player coin pick game
mediumPlayers alternately take a number from either end of the array and both play optimally. Let dp[i][j] be the best score difference (current player minus opponent) on a[i..j]. Taking the left end gives a[i] - dp[i+1][j], the right end gives a[j] - dp[i][j-1]. Player 1 wins or ties if dp[0][n-1] is at least 0. Time O(n^2), space O(n) with a rolling array, O(n^2) as written. Edge cases: one element (player 1 wins), tie counts as a win for player 1, all equal values, even length where player 1 can always tie or win.
pythondef predict_winner(a): n = len(a) dp = [[0] * n for _ in range(n)] for i in range(n): dp[i][i] = a[i] for length in range(2, n + 1): for i in range(n - length + 1): j = i + length - 1 dp[i][j] = max(a[i] - dp[i + 1][j], a[j] - dp[i][j - 1]) return dp[0][n - 1] >= 0javaboolean predictWinner(int[] a) { int n = a.length; int[][] dp = new int[n][n]; for (int i = 0; i < n; i++) dp[i][i] = a[i]; for (int len = 2; len <= n; len++) for (int i = 0; i + len - 1 < n; i++) { int j = i + len - 1; dp[i][j] = Math.max(a[i] - dp[i + 1][j], a[j] - dp[i][j - 1]); } return dp[0][n - 1] >= 0; }4 Matrix chain multiplication: fewest scalar multiplications
mediumMatrix i has dimensions p[i] by p[i+1]. Let dp[i][j] be the cheapest way to multiply matrices i to j. Try every split point k: dp[i][k] + dp[k+1][j] + p[i] * p[k+1] * p[j+1], the last term being the cost of multiplying the two resulting matrices. A single matrix costs 0. Time O(n^3), space O(n^2). Edge cases: a single matrix (0), two matrices (one product), parenthesisation matters even though the result matrix is the same.
pythondef matrix_chain(p): # p has n + 1 entries for n matrices n = len(p) - 1 dp = [[0] * n for _ in range(n)] for length in range(2, n + 1): for i in range(n - length + 1): j = i + length - 1 dp[i][j] = min(dp[i][k] + dp[k + 1][j] + p[i] * p[k + 1] * p[j + 1] for k in range(i, j)) return dp[0][n - 1] if n else 0javaint matrixChain(int[] p) { int n = p.length - 1; int[][] dp = new int[n][n]; for (int len = 2; len <= n; len++) for (int i = 0; i + len - 1 < n; i++) { int j = i + len - 1; dp[i][j] = Integer.MAX_VALUE; for (int k = i; k < j; k++) dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k + 1][j] + p[i] * p[k + 1] * p[j + 1]); } return n == 0 ? 0 : dp[0][n - 1]; }5 Minimum score triangulation of a polygon
mediumVertices carry values and a triangle scores the product of its vertex values. For the chord from i to j, choose the third vertex k between them: dp[i][j] = min over k of dp[i][k] + dp[k][j] + v[i] * v[k] * v[j]. Intervals with fewer than three vertices cost 0. Time O(n^3), space O(n^2). Edge cases: a triangle (single product), many vertices of value 1, the chord must span at least two steps.
pythondef min_score_triangulation(v): n = len(v) dp = [[0] * n for _ in range(n)] for length in range(3, n + 1): for i in range(n - length + 1): j = i + length - 1 dp[i][j] = min(dp[i][k] + dp[k][j] + v[i] * v[k] * v[j] for k in range(i + 1, j)) return dp[0][n - 1]javaint minScoreTriangulation(int[] v) { int n = v.length; int[][] dp = new int[n][n]; for (int len = 3; len <= n; len++) for (int i = 0; i + len - 1 < n; i++) { int j = i + len - 1; dp[i][j] = Integer.MAX_VALUE; for (int k = i + 1; k < j; k++) dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k][j] + v[i] * v[k] * v[j]); } return dp[0][n - 1]; }6 Minimum cost to cut a stick
hardA cut costs the current length of the piece being cut. Sort the cut positions and add 0 and n as boundaries. dp[i][j] is the minimum cost to make all cuts strictly between boundary i and boundary j. Choose the first cut k there: cost cuts[j] - cuts[i] plus the cost of each side. Thinking of the last cut as an interval split is what makes subproblems independent. Time O(m^3) for m cuts, space O(m^2). Edge cases: no cuts (0), a single cut (n), unsorted input (sort first), cuts at the ends are not allowed by the statement.
pythondef min_cost(n, cuts): c = [0] + sorted(cuts) + [n] m = len(c) dp = [[0] * m for _ in range(m)] for length in range(2, m): for i in range(m - length): j = i + length dp[i][j] = min(dp[i][k] + dp[k][j] for k in range(i + 1, j)) + c[j] - c[i] return dp[0][m - 1]javaint minCost(int n, int[] cuts) { int[] c = new int[cuts.length + 2]; System.arraycopy(cuts, 0, c, 1, cuts.length); Arrays.sort(c); c[c.length - 1] = n; int m = c.length; int[][] dp = new int[m][m]; for (int len = 2; len < m; len++) for (int i = 0; i + len < m; i++) { int j = i + len; dp[i][j] = Integer.MAX_VALUE; for (int k = i + 1; k < j; k++) dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k][j]); dp[i][j] += c[j] - c[i]; } return dp[0][m - 1]; }7 Guess number higher or lower II: minimum money to guarantee a win
mediumGuessing k wrongly costs k and leaves you the worse of the two sides, so dp[i][j] = min over k in [i, j] of k + max(dp[i][k-1], dp[k+1][j]). Empty or single-number ranges cost 0. The minimax structure plus an interval state is typical of such games. Time O(n^3), space O(n^2). Edge cases: n equal to 1 (0), n equal to 2 (1), arrays sized n + 2 so k - 1 and k + 1 are valid, worst-case rather than average cost.
pythondef get_money_amount(n): dp = [[0] * (n + 2) for _ in range(n + 2)] for length in range(2, n + 1): for i in range(1, n - length + 2): j = i + length - 1 dp[i][j] = min(k + max(dp[i][k - 1], dp[k + 1][j]) for k in range(i, j + 1)) return dp[1][n]javaint getMoneyAmount(int n) { int[][] dp = new int[n + 2][n + 2]; for (int len = 2; len <= n; len++) for (int i = 1; i + len - 1 <= n; i++) { int j = i + len - 1; dp[i][j] = Integer.MAX_VALUE; for (int k = i; k <= j; k++) dp[i][j] = Math.min(dp[i][j], k + Math.max(dp[i][k - 1], dp[k + 1][j])); } return dp[1][n]; }8 Burst balloons: maximum coins
hardBursting balloon k earns nums[i] * nums[k] * nums[j] for its current neighbours. Thinking forward makes subproblems depend on each other. Instead choose the last balloon k to burst in an open interval (i, j): its neighbours are then the fixed boundaries i and j. dp[i][j] = max over k of dp[i][k] + dp[k][j] + nums[i] * nums[k] * nums[j]. Pad the array with 1 on both ends. Time O(n^3), space O(n^2). Edge cases: empty array (0), a single balloon, zeros in the array, picking the last burst rather than the first.
pythondef max_coins(nums): a = [1] + nums + [1] n = len(a) dp = [[0] * n for _ in range(n)] for length in range(2, n): for i in range(n - length): j = i + length dp[i][j] = max(dp[i][k] + dp[k][j] + a[i] * a[k] * a[j] for k in range(i + 1, j)) return dp[0][n - 1]javaint maxCoins(int[] nums) { int n = nums.length + 2; int[] a = new int[n]; a[0] = a[n - 1] = 1; for (int i = 0; i < nums.length; i++) a[i + 1] = nums[i]; int[][] dp = new int[n][n]; for (int len = 2; len < n; len++) for (int i = 0; i + len < n; i++) { int j = i + len; for (int k = i + 1; k < j; k++) dp[i][j] = Math.max(dp[i][j], dp[i][k] + dp[k][j] + a[i] * a[k] * a[j]); } return dp[0][n - 1]; }9 Strange printer: fewest turns to print a string
hardThe printer prints a run of one character per turn and may overwrite earlier output. Remove consecutive duplicates first. dp[i][j] is the fewest turns for s[i..j]. Printing s[i] alone costs 1 + dp[i+1][j]. If s[k] equals s[i] for some k in (i, j], the first print can be extended to cover k for free: dp[i+1][k-1] + dp[k][j]. Time O(n^3), space O(n^2). Edge cases: empty string (0), all one letter (1), duplicates removed first, a split where dp[i+1][k-1] refers to an empty range (0).
pythondef strange_printer(s): s = ''.join(c for i, c in enumerate(s) if i == 0 or c != s[i - 1]) n = len(s) if n == 0: return 0 dp = [[0] * n for _ in range(n)] for i in range(n - 1, -1, -1): dp[i][i] = 1 for j in range(i + 1, n): dp[i][j] = 1 + dp[i + 1][j] for k in range(i + 1, j + 1): if s[k] == s[i]: left = dp[i + 1][k - 1] if i + 1 <= k - 1 else 0 dp[i][j] = min(dp[i][j], left + dp[k][j]) return dp[0][n - 1]javaint strangePrinter(String str) { StringBuilder sb = new StringBuilder(); for (int i = 0; i < str.length(); i++) if (i == 0 || str.charAt(i) != str.charAt(i - 1)) sb.append(str.charAt(i)); String s = sb.toString(); int n = s.length(); if (n == 0) return 0; int[][] dp = new int[n][n]; for (int i = n - 1; i >= 0; i--) { dp[i][i] = 1; for (int j = i + 1; j < n; j++) { dp[i][j] = 1 + dp[i + 1][j]; for (int k = i + 1; k <= j; k++) if (s.charAt(k) == s.charAt(i)) dp[i][j] = Math.min(dp[i][j], (i + 1 <= k - 1 ? dp[i + 1][k - 1] : 0) + dp[k][j]); } } return dp[0][n - 1]; }10 Minimum cost to merge stones into one pile
hardEach move merges exactly K consecutive piles at a cost equal to their total. It is only possible if (n - 1) % (K - 1) == 0. dp[i][j] is the minimum cost to reduce stones i..j to as few piles as possible. Split at m, stepping by K - 1, so the left part reduces to one pile and the right to K - 1. When the interval can become exactly one pile, add the interval total from a prefix sum. Time O(n^3 / K), space O(n^2). Edge cases: impossible counts (return -1), a single pile (0), K equal to 2 (the classic version), the step of K - 1 on the split.
pythondef merge_stones(stones, K): n = len(stones) if (n - 1) % (K - 1): return -1 pre = [0] for x in stones: pre.append(pre[-1] + x) INF = float('inf') dp = [[0] * n for _ in range(n)] for length in range(2, n + 1): for i in range(n - length + 1): j = i + length - 1 dp[i][j] = min(dp[i][m] + dp[m + 1][j] for m in range(i, j, K - 1)) if (j - i) % (K - 1) == 0: dp[i][j] += pre[j + 1] - pre[i] return dp[0][n - 1]javaint mergeStones(int[] stones, int K) { int n = stones.length; if ((n - 1) % (K - 1) != 0) return -1; int[] pre = new int[n + 1]; for (int i = 0; i < n; i++) pre[i + 1] = pre[i] + stones[i]; int[][] dp = new int[n][n]; for (int len = 2; len <= n; len++) for (int i = 0; i + len - 1 < n; i++) { int j = i + len - 1; dp[i][j] = Integer.MAX_VALUE; for (int m = i; m < j; m += K - 1) dp[i][j] = Math.min(dp[i][j], dp[i][m] + dp[m + 1][j]); if ((j - i) % (K - 1) == 0) dp[i][j] += pre[j + 1] - pre[i]; } return dp[0][n - 1]; }
Frequently asked questions
How do I recognise an interval DP problem?
The input is a sequence, operations act on contiguous parts, and the best result for a range depends on how you split it. States are naturally written dp[i][j].
Why choose the last operation rather than the first?
After the last operation the interval splits into two independent parts with known boundaries, so each part can be solved separately. With the first operation, later neighbours change and break independence.
What is the complexity of interval DP?
Usually O(n^2) states with an O(n) split search, giving O(n^3). If only endpoints matter and no split is searched, it is O(n^2).
Are interval DP questions common in interviews?
They are harder and less frequent, but appear as challenge questions at product companies. The DSA coding round guide helps you decide how much time to spend on them.
Related guides
More in DSA Interview Questions
- Interval interview questions with worked solutions
- Kadane algorithm interview questions with worked solutions
- KMP and string matching interview questions with solutions
- Knapsack DP Interview Questions
- Linked list interview questions with worked solutions
- Longest Common Subsequence (LCS) Interview Questions
- Longest Increasing Subsequence (LIS) Interview Questions
- LRU Cache and Design Data Structure Interview Questions
- Math and number theory interview questions with solutions
- Matrix interview questions with worked solutions
- Merge intervals pattern questions with worked solutions
- Minimum Spanning Tree Interview Questions