Interval Dynamic Programming for Coding Interviews: Burst Balloons, Matrix Chains and Beyond

Some of the hardest dynamic programming questions in coding interviews share one shape: the answer for a range [i, j] depends on splitting that range at some point k and combining the answers for the smaller ranges. This family is called interval DP. Once you recognize the pattern, problems like Burst Balloons, Matrix Chain Multiplication, Minimum Cost to Cut a Stick and Palindrome Partitioning become variations of the same template. THE TEMPLATE Define dp[i][j] as the best answer for the subarray or substring from i to j. Then: dp[i][j] = best over k in [i..j] of combine(dp[i][k], dp[k][j], cost(i, k, j)) The crucial detail is the iteration order. Because dp[i][j] depends on smaller intervals, fill the table by increasing interval length: for length in range(2, n + 1): for i in range(0, n - length + 1): j = i + length - 1 for k in range(i, j): ... Most interval DP solutions are O(n^3) time and O(n^2) space, which is fine for n up to a few hundred. EXAMPLE 1: MATRIX CHAIN MULTIPLICATION Given matrix dimensions, find the cheapest order to multiply them. If matrix i has shape dims[i] x dims[i+1], then splitting the chain i..j at k costs: dp[i][k] + dp[k+1][j] + dims[i] * dims[k+1] * dims[j+1] This is the textbook interval DP and a great one to explain first if the interviewer asks about the general technique. EXAMPLE 2: BURST BALLOONS Bursting balloon k earns nums[left] * nums[k] * nums[right], and neighbors change after every burst, which makes the problem look impossible to break down. The trick is to think of k as the LAST balloon burst in the interval (i, j). When k is last, its neighbors are exactly the boundaries i and j, so the two sides become independent: pad nums with 1 at both ends dp[i][j] = max over k in (i, j) of dp[i][k] + dp[k][j] + nums[i] * nums[k] * nums[j] Explaining the "last instead of first" insight is what interviewers are really looking for. Say it out loud before you code. EXAMPLE 3: MINIMUM COST TO CUT A STICK Each cut costs the current length of the piece. Sort the cut positions, add 0 and the stick length as boundaries, and let dp[i][j] be the cheapest way to make all cuts strictly between boundary i and boundary j: dp[i][j] = min over k in (i, j) of dp[i][k] + dp[k][j] + (cuts[j] - cuts[i]) It's almost the same recurrence as Burst Balloons, which is worth pointing out. EXAMPLE 4: STRING PROBLEMS - Longest palindromic subsequence: dp[i][j] = dp[i+1][j-1] + 2 if s[i] == s[j], else max(dp[i+1][j], dp[i][j-1]). - Minimum insertions to make a palindrome: n minus the longest palindromic subsequence. - Strange printer and remove boxes: harder variants with extra state. HOW TO SPOT INTERVAL DP - The input is a sequence, and the operation merges, splits or removes elements. - Choices change what is adjacent to what. - Greedy approaches have obvious counterexamples. - n is small (often 500 or less), which hints that O(n^3) is acceptable. COMMON MISTAKES - Iterating i and j in the wrong order, so you read states that haven't been computed. - Off-by-one errors on whether k is inclusive. - Forgetting to pad boundaries (Burst Balloons, stick cutting). HOW TO PRESENT IT Start with the recursive definition and a memoized version; it's often easier to get right under pressure. Then convert it to the bottom-up table if time allows. Some candidates use Linkjob AI (https://linkjob.ai), which gives real-time help during live job interviews and technical interviews, to keep their explanation organized when a hard DP problem appears. With the template in your pocket, interval DP stops being a guessing game and becomes a pattern you can apply with confidence.