Matrix chain multiplication, burst balloons — solve range-based DP problems.
Published September 21, 2026
Some problems are about a contiguous range (a subarray, substring, or segment) where the best answer for the whole range depends on how you split it, or on which element you handle last. Interval DP solves them by computing an answer for every sub-range [i..j], from shortest to longest, so that when you solve a range, every smaller range inside it is already solved.
It's recognisable from a few signals:
dp[i][j] = best answer for the sub-range i..j
for len = 1 .. n: # shorter ranges first
for i = 0 .. n - len:
j = i + len - 1
dp[i][j] = best over k in [i..j] of combine(dp[i][k-ish], dp[k-ish][j], cost(i, k, j))
There are O(n²) ranges, and each tries O(n) split points, so the typical cost is O(n³) time and O(n²) space, fine up to n in the low hundreds. The loop order is essential. Iterating by length (not by i then j) guarantees that the smaller ranges a range depends on are computed first.
The hardest part is always choosing what k means: "where I split" or "which element I do last".
Multiplying matrices A(10×30) · B(30×5) · C(5×60) costs different amounts depending on the grouping:
Find the grouping with the fewest scalar multiplications. With dims such that matrix i is dims[i] × dims[i+1]:
int matrixChain(int[] dims) {
int n = dims.length - 1; // number of matrices
int[][] dp = new int[n][n]; // dp[i][j] = min cost to multiply matrices i..j
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++) { // split: (i..k)(k+1..j), the last multiplication
int cost = dp[i][k] + dp[k + 1][j] + dims[i] * dims[k + 1] * dims[j + 1];
dp[i][j] = Math.min(dp[i][j], cost);
}
}
}
return dp[0][n - 1];
}
Ranges of length 1 (a single matrix) cost 0, which the default array value already provides.
Balloons have numbers. Bursting balloon i earns left × nums[i] × right, where left and right are its current neighbours. Maximize the total.
Thinking about which balloon to burst first fails, because after it bursts, its neighbours change, and the two sides become connected. The trick is to choose the balloon burst last in a range. If balloon k is the last one burst between boundaries i and j (exclusive), then while everything else in the range is being burst, k is still standing, so the left part and the right part are independent. When k finally bursts, its neighbours are exactly the boundaries i and j.
int maxCoins(int[] nums) {
int n = nums.length;
int[] b = new int[n + 2]; // pad with virtual 1s at both ends
b[0] = b[n + 1] = 1;
for (int i = 0; i < n; i++) b[i + 1] = nums[i];
int[][] dp = new int[n + 2][n + 2]; // dp[i][j] = best for balloons strictly between i and j
for (int len = 2; len <= n + 1; len++) { // distance between the boundaries
for (int i = 0; i + len <= n + 1; i++) {
int j = i + len;
for (int k = i + 1; k < j; k++) { // k = the LAST balloon burst in (i, j)
dp[i][j] = Math.max(dp[i][j], dp[i][k] + b[i] * b[k] * b[j] + dp[k][j]);
}
}
}
return dp[0][n + 1];
}
The padding with 1s handles the edges without special cases. "Last instead of first" is the key idea to remember for any problem where removing an element changes its neighbours.
A stick of length n with required cut positions. Each cut costs the length of the piece being cut. Minimize the total.
Again, consider the first cut within a segment. It costs the whole segment's length, and splits the segment into two independent segments. Add the endpoints 0 and n, sort the positions, and work on ranges between cut positions:
int minCost(int n, int[] cuts) {
int m = cuts.length;
int[] c = new int[m + 2];
c[0] = 0; c[m + 1] = n;
for (int i = 0; i < m; i++) c[i + 1] = cuts[i];
Arrays.sort(c);
int[][] dp = new int[m + 2][m + 2]; // dp[i][j] = min cost to make all cuts strictly between c[i] and c[j]
for (int len = 2; len <= m + 1; len++) {
for (int i = 0; i + len <= m + 1; 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] + (c[j] - c[i]));
}
}
return dp[0][m + 1];
}
The DP runs over the cut positions (m + 2 of them), not over the stick's length, so it's O(m³) regardless of how long the stick is.
dp[i][j] = dp[i+1][j-1] + 2 if the ends match, else max(dp[i+1][j], dp[i][j-1]).isPal[i][j] with interval DP, then run a 1-D DP over cut positions.These only look at the ends of the range instead of all split points, so they're O(n²).
The same recurrence can be written recursively with memoization, solve(i, j), which is often easier to derive first. It avoids thinking about loop order, because recursion naturally solves smaller ranges first. Convert it to the bottom-up form if recursion depth or overhead is a concern.
Q: Why must the outer loop be over length?
A: dp[i][j] depends on strictly shorter ranges inside it. Iterating by increasing length guarantees they're all computed first. Iterating i from 0 upwards with j inside would read dp[k+1][j] before it's been filled in.
Q: Why does Burst Balloons pick the last balloon rather than the first? A: Bursting one first merges its neighbours, so the left and right parts stop being independent subproblems. If k is the last balloon in the range, it stays in place while both sides are processed, so the sides are independent, and k's final neighbours are the fixed range boundaries.
Q: What's the complexity, and can it be improved? A: Typically O(n³) time and O(n²) space. Some problems with special cost structure, such as the classic optimal binary search tree, admit Knuth's optimization, which restricts the split points and gives O(n²). In interviews, O(n³) is expected.
Q: How do you reconstruct the optimal split, not just its cost?
A: Store the best k for each range in a second table, split[i][j], then recursively rebuild the parenthesization or order from split[0][n-1].
Q: How do you recognise an interval DP problem? A: The answer for a range depends on combining answers for sub-ranges, the operations change adjacency or merge pieces, and you're asked for an optimum over all orders of operations. Asking "what happens last?" or "where is the first split?" usually reveals the recurrence.