Why this matters
Many problems ask for the best order to do a set of steps, where each step depends on what is still left. A game might pay out more when a tile is removed while its neighbours are still there. A build system might compile files in an order where each file needs the ones before it. A tool that merges a row of files might pay a cost that depends on the two files next to each one.
These problems look hard at first, because the order matters and there are too many orders to try. Interval dynamic programming (interval DP) is a method for them. An interval here means a range of positions from l to r, and the method solves the small ranges first and uses their answers to solve the bigger ranges. The memoization and tabulation lessons in this module introduced the idea of storing answers in a table. This lesson uses a table indexed by two positions, and it builds on that idea.
You need C++ std::vector, loops and long long from earlier modules. The problem below is the balloon problem, which is a classic exercise. Each step is a balloon burst, and the score of a burst depends on the balloons next to it.
The problem in plain words
You have a row of balloons. Each balloon has a number painted on it. You pop the balloons one at a time, in an order you choose. When you pop balloon i, you get coins equal to the number on its left neighbour, times the number on balloon i, times the number on its right neighbour. The neighbours are the balloons next to i that are still in the row at that moment. A popped balloon is removed from the row, so the neighbours of the others change as you go.
If there is no balloon on one side, that side counts as the number 1. So the edge balloons still give coins. The question is: in what order should you pop the balloons to get the most coins?
Take the row 3, 1, 5. Here are two orders.
- Pop
1first. Its neighbours are3and5, so you get3 * 1 * 5 = 15coins. The row is now3, 5. Pop3next. Its neighbours are the number 1 on the left edge and5, so you get1 * 3 * 5 = 15coins. Pop5last. Its neighbours are both edges, so you get1 * 5 * 1 = 5coins. The total is 35. - Pop
3first. Its neighbours are the left edge (1) and1, so you get1 * 3 * 1 = 3coins. Then pop1, with neighbours edge and5, for1 * 1 * 5 = 5coins. Then pop5for5coins. The total is 13.
The first order is better. The job is to find the best order without trying all of them.
Two terms need a plain definition. A permutation is one ordering of a set of items. The row 3, 1, 5 has three balloons, so there are 3 times 2 times 1, which is 6, orders to try. A row of 10 balloons has 3,628,800 orders. The table method in this lesson avoids trying them all.
Why the first burst is the wrong thing to think about
A natural idea is to ask which balloon to pop first. Suppose you pop balloon i first. Then the row splits into the balloons to its left and the balloons to its right, but the two sides are not separate problems. The balloon you popped first is gone, so the balloons on the left and right now touch each other across the gap. Their neighbours change, and the score of each later pop depends on that.
The left side and the right side are linked through the popped balloon. If you try to solve the left side on its own, you do not know which balloon on the right will end up next to it. So the two sides are not independent. The solution has to remember the state of the whole row at each step, and that grows too quickly.
The fix is to think about the last balloon to pop instead.
The idea: think about the last balloon in a range
Pick two balloons that will still be in the row at the end, call them l and r. They act as walls. Every balloon strictly between them is popped before the walls go. Now look at all the balloons between l and r. One of them is popped last. Call that one k.
When k is popped, every other balloon between l and r is already gone. So the only balloons left in that range are l, k and r. The neighbours of k at that moment are exactly l and r. So the coins from popping k are fixed: nums[l] * nums[k] * nums[r]. The choice of k decides this value.
Now look at what happens before k is popped. The balloons between l and k are popped while k is still there. Since k is still alive, it acts as a wall for them, exactly as l and r act as walls for the whole range. So the balloons between l and k form a smaller problem with walls l and k. The same is true on the right: the balloons between k and r form a smaller problem with walls k and r.
These two smaller problems do not depend on each other. Neither side can change the walls of the other, because k stays in place until the very end of this range. This is the point of the method. Choosing the last balloon splits one range into two ranges, and each one can be solved on its own.
So the answer for the range from l to r is:
best over every k between l and r of: (best for the range from l to k) + (best for the range from k to r) + nums[l] * nums[k] * nums[r]
Each smaller range is an interval, and the table stores the answer for every interval. That is why this is called interval DP.
Sentinels at both ends
The walls at the very ends of the row are a problem. The leftmost balloon has no real left neighbour, and the rightmost has no real right neighbour. The rule says that a missing neighbour counts as 1. If the code handles that with an if at each step, it gets messy.
A sentinel is an extra value added to a list so that the edge cases become ordinary cases. Here, add a 1 at the front and a 1 at the back of the row. The row 3, 1, 5, 8 becomes 1, 3, 1, 5, 8, 1. The two new 1s are never popped. They act as the walls for the whole problem, and their value is 1, which matches the rule for a missing neighbour.
With sentinels, the table can use l = 0 and r = n - 1 for the full problem, where n is the length of the new row. The sentinels are not popped, so the answer for the whole problem is the table entry for the range from the first sentinel to the last one.
The table and what each entry means
Let a be the row with sentinels, and let n be its length. Define a table dp with n rows and n columns. The entry dp[l][r] is the most coins you can get by popping every balloon strictly between positions l and r, while the balloons at l and r stay in place.
Two facts set up the table.
- If
r - lis 1, there is nothing betweenlandr. The entry is 0. This is the base case, the answer you know without work. - The answer you want is
dp[0][n - 1], which covers every real balloon, because the sentinels sit at positions 0 andn - 1.
The rule that fills the other entries is the one from the previous section. For dp[l][r] with r - l at least 2, try every k strictly between l and r, and keep the best value of dp[l][k] + dp[k][r] + a[l] * a[k] * a[r].
The order of filling matters. The entry dp[l][r] needs dp[l][k] and dp[k][r], and both of those cover smaller ranges. So fill the table by range length: first all ranges of length 2, then length 3, and so on. Filling by length guarantees that the smaller ranges are ready when they are needed.
Worked example 1: 3, 1, 5, 8
Add the sentinels. The row becomes a = [1, 3, 1, 5, 8, 1], with 6 positions numbered 0 to 5. The real balloons are at positions 1 to 4. The answer is dp[0][5].
Work through the lengths in order. Each line below is one table entry, with the best choice of k in brackets.
- Length 2 entries:
dp[0][2]covers the balloon3. Its only choice isk = 1, so the value is1 * 3 * 1 = 3. The entrydp[1][3]covers the balloon1, so the value is3 * 1 * 5 = 15. The entrydp[2][4]covers the balloon5, so the value is1 * 5 * 8 = 40. The entrydp[3][5]covers the balloon8, so the value is5 * 8 * 1 = 40. - Length 3 entry:
dp[0][3]covers balloons3and1. Two choices are possible. Withk = 1(balloon3last), the value isdp[0][1] + dp[1][3] + 1 * 3 * 5 = 0 + 15 + 15 = 30. Withk = 2(balloon1last), the value isdp[0][2] + dp[2][3] + 1 * 1 * 5 = 3 + 0 + 5 = 8. The best is 30. - The table continues the same way. The values that matter for the answer are
dp[2][5] = 48,dp[1][4] = 135,dp[0][4] = 159anddp[0][5] = 167.
The final choice for dp[0][5] is k = 4, which is the balloon 8. That means 8 is popped last. Its neighbours at that moment are the two sentinels, so it gives 1 * 8 * 1 = 8 coins. The left part, dp[0][4] = 159, covers 3, 1, 5, and the right part, dp[4][5] = 0, has no balloons.
You can check the total by writing out one burst order that reaches 167. Here is one, with the neighbours at each pop.
| Burst | Left and right neighbours | Coins |
|---|---|---|
| 1 | 3 and 5 | 3 * 1 * 5 = 15 |
| 5 | 3 and 8 | 3 * 5 * 8 = 120 |
| 3 | sentinel 1 and 8 | 1 * 3 * 8 = 24 |
| 8 | sentinel 1 and sentinel 1 | 1 * 8 * 1 = 8 |
The total is 15 + 120 + 24 + 8, which is 167. The table gives this order when you read its choices from the top. The entry dp[0][5] picks 8 as the last pop. The entry dp[0][4] picks 3 as the last pop inside its range. The entry dp[1][4] picks 5 as the last pop inside its range, and the range dp[1][3] has only the 1 left. So the order from first to last is 1, 5, 3, 8.
The code
The program below builds the sentinel row, fills the table by length, and returns dp[0][n - 1]. It also has a brute force function that tries every order. The brute force is slow, so it runs only on short rows, and it checks the table on those rows.
#include <algorithm>
#include <iostream>
#include <numeric>
#include <vector>
// Largest total coins when every balloon is burst once.
// a = [1, nums..., 1]; dp[l][r] = best coins from bursting every balloon
// strictly between l and r, while l and r stay in place.
long long maxCoins(const std::vector<int>& nums) {
std::vector<long long> a;
a.reserve(nums.size() + 2);
a.push_back(1);
a.insert(a.end(), nums.begin(), nums.end());
a.push_back(1);
const int n = static_cast<int>(a.size());
std::vector<std::vector<long long>> dp(n, std::vector<long long>(n, 0));
for (int len = 2; len < n; ++len) { // gap between l and r
for (int l = 0; l + len < n; ++l) {
const int r = l + len;
long long best = 0;
for (int k = l + 1; k < r; ++k) { // k is the last balloon burst in (l, r)
const long long coins = dp[l][k] + dp[k][r] + a[l] * a[k] * a[r];
best = std::max(best, coins);
}
dp[l][r] = best;
}
}
return dp[0][n - 1];
}
// Try every burst order (only for tiny inputs) to check the table.
long long bruteForce(const std::vector<int>& nums) {
const int n = static_cast<int>(nums.size());
std::vector<int> order(n);
std::iota(order.begin(), order.end(), 0);
long long best = 0;
do {
std::vector<bool> alive(n, true);
long long total = 0;
for (int i : order) {
int left = i - 1;
while (left >= 0 && !alive[left]) --left;
int right = i + 1;
while (right < n && !alive[right]) ++right;
const long long lv = (left >= 0) ? nums[left] : 1;
const long long rv = (right < n) ? nums[right] : 1;
total += lv * nums[i] * rv;
alive[i] = false;
}
best = std::max(best, total);
} while (std::next_permutation(order.begin(), order.end()));
return best;
}
int main() {
const std::vector<std::vector<int>> cases = {
{3, 1, 5, 8}, {1, 5}, {}, {7}, {2, 4, 6}, {9, 76, 64, 21}, {1, 2, 3, 4, 5, 6, 7}, {3, 1, 5, 8, 2, 9, 4}};
for (const auto& c : cases) {
std::cout << "dp=" << maxCoins(c);
if (c.size() <= 7) std::cout << " brute=" << bruteForce(c);
std::cout << "\n";
}
}Compile and run it with:
g++ -std=c++20 -Wall -o balloons balloons.cpp
./balloonsThe program prints this, with no compiler warnings:
dp=167 brute=167
dp=10 brute=10
dp=0 brute=0
dp=7 brute=7
dp=66 brute=66
dp=116718 brute=116718
dp=504 brute=504
dp=778 brute=778The first line is the worked example from above. The empty row gives 0, because there are no balloons to pop. The row {7} gives 7, because one balloon between two sentinels gives 1 * 7 * 1. The table and the brute force agree on every row, including the rows of length 4 and 7.
The bruteForce function uses std::next_permutation, which rearranges a vector into the next ordering each time it is called. Starting from the sorted order 0, 1, 2, ..., the loop visits every ordering once. That is n! orders, where n! means n times n minus 1 times and so on down to 1. For 7 balloons that is 5,040 orders, which is fast. For 12 balloons it would be about 479 million, which is too slow.
Worked example 2: 9, 76, 64, 21
This row has larger numbers. Each balloon is still popped once and the method is the same, so the code needs no change. The program prints 116718. The brute force tries all 4! = 24 orders and also finds 116718.
The point of this example is that the numbers do not change the method. The table looks at the structure, which is the walls and the last choice, not at the values.
Worked example 3: 3, 1, 5, 8, 2, 9, 4
This row has 7 balloons, so the brute force tries 7! = 5,040 orders. The program prints 778 for both methods. With sentinels the row has 9 positions, and the table fills 28 entries, one for each interval of length 2 or more, as Exercise 3 below shows for any n.
If you grow the row to 30 balloons, the brute force would need 30! orders, which is far too many to run. The table for 30 balloons has 465 entries, and each entry tries at most 30 choices of k. That is a small amount of work, which is why the method is useful. The brute force is only a check on small inputs.
Common mistakes
Forgetting the sentinels. If the code does not add the 1s at both ends, the edge balloons have no left or right neighbour, and the code reads outside the vector. The next program shows the same kind of failure. It reads the position before the start of a 4-element vector, using at(), which checks the position and throws an error when it is outside the vector.
#include <cstdint>
#include <vector>
int main() {
std::vector<int> v(4, 1);
return v.at(static_cast<std::size_t>(-1));
}Compiled with g++ -std=c++20 -Wall -o errs errs.cpp, the program stops with this message.
terminate called after throwing an instance of 'std::out_of_range'
what(): vector::_M_range_check: __n (which is 18446744073709551615) >= this->size() (which is 4)The index -1 becomes a very large unsigned number, which is why the message shows 18446744073709551615. The fix is the sentinel row, so the code never reads position -1.
Looping k from l to r instead of l + 1 to r - 1. The value k must be a balloon strictly between the walls. If k equals l or r, the formula uses a wall as the balloon being popped, and it reads dp[l][r] while that entry is still being computed. The loop bounds in the code, k = l + 1 and k < r, prevent that.
Filling the table in the wrong order. The entry dp[l][r] needs the entries dp[l][k] and dp[k][r], which cover smaller ranges. If the outer loop walks l forward and the inner loop walks r forward, some of those smaller entries are still zero when they are read. The program runs without an error and can print a wrong total. Filling by length, as the code does, avoids this.
Comparing a signed loop counter with size(). The size() function of a vector returns an unsigned type, and comparing it with an int loop counter gives a warning. This program does that.
#include <vector>
int main() {
std::vector<int> nums = {3, 1, 5};
int total = 0;
for (int i = 0; i < nums.size(); ++i) total += nums[i];
return total;
}Compiled with g++ -std=c++20 -Wall -c -o /dev/null signed.cpp, the compiler prints this.
signed.cpp: In function ‘int main()’:
signed.cpp:6:23: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<int>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
6 | for (int i = 0; i < nums.size(); ++i) total += nums[i];
| ~~^~~~~~~~~~~~~The fix is to store the length as int, as the code does with const int n = static_cast<int>(a.size());, or to use std::size_t for the counter.
Using int for the coins. If each number is at most 100, a single pop can give up to 100 times 100 times 100, which is a million. Many pops add up, so the total can grow large. The code uses long long, which holds values far beyond the range of int.
Practice
Exercise 1. Find the best total for the row 2, 3 by hand. Try both orders and state the coins from each pop.
Show the answer. Pop 2 first. Its neighbours are the left edge (1) and 3, so it gives 1 * 2 * 3 = 6 coins. Then pop 3 with neighbours edge and edge, for 1 * 3 * 1 = 3 coins. The total is 9. The other order pops 3 first, with neighbours 2 and edge, for 2 * 3 * 1 = 6 coins, then pops 2 for 1 * 2 * 1 = 2 coins, which is 8. The best total is 9, which the program also prints.
Exercise 2. The row 1, 2, 3 has the best total 12. Find the burst order that gives 12, and write the coins for each pop.
Show the answer. Pop 2 first. Its neighbours are 1 and 3, so it gives 1 * 2 * 3 = 6 coins. The row is now 1, 3. Pop 1 next, with neighbours edge and 3, for 1 * 1 * 3 = 3 coins. Pop 3 last, with neighbours edge and edge, for 1 * 3 * 1 = 3 coins. The total is 6 + 3 + 3, which is 12.
Exercise 3. A row has n real balloons. The table has entries dp[l][r] for every pair of positions with r - l at least 2. Show that the number of such entries is n * (n + 1) / 2.
Show the answer. With sentinels the row has m = n + 2 positions, numbered 0 to m - 1. The number of pairs l < r in a row of m positions is m * (m - 1) / 2. The pairs with r - l equal to 1 are the m - 1 neighbouring pairs, and those are base cases that are not computed. So the count is m * (m - 1) / 2 - (m - 1), which equals (m - 1) * (m - 2) / 2. Put m = n + 2 in that formula to get (n + 1) * n / 2. For n = 3, the answer is 6. The pairs are (0,2), (0,3), (0,4), (1,3), (1,4) and (2,4) in a row of 5 positions.
Exercise 4. The row 3, 1, 5, 8 becomes a = [1, 3, 1, 5, 8, 1] with sentinels. The entry dp[0][4] covers the balloons at positions 1 to 3, which are 3, 1 and 5, between the walls at position 0 and position 4. Its value is 159. Find the balloon that is popped last inside this range, and give the two smaller entries it uses.
Show the answer. The best choice is k = 1, the balloon 3, so 3 is popped last inside this range. Its coins are a[0] * a[1] * a[4] = 1 * 3 * 8 = 24, because its walls are the sentinel 1 and the balloon 8. The left entry is dp[0][1], which covers no balloons, so it is 0. The right entry is dp[1][4], which covers the balloons 1 and 5 between the walls 3 and 8, and its value is 135. The total is 0 + 135 + 24, which is 159.
Exercise 5. Explain in your own words why the method asks "which balloon is popped last" and not "which balloon is popped first".
Show the answer. When you pop a balloon first, its two neighbours become next to each other, and the two sides of the row depend on each other through that gap. When you pop a balloon last in a range, it stays in place for the whole time, so it is a wall for both sides. The two sides can then be solved on their own, and their answers can be added. The choice of the last balloon turns one problem into two smaller ones that do not interact.
Summary
- Think about the last balloon popped in a range, because that balloon is a fixed wall for everything before it.
- The last balloon's coins depend only on the two walls of its range, so the two sides of the range can be solved separately.
- Add a 1 at both ends of the row. The sentinels remove the edge cases and make the full answer
dp[0][n - 1]. - Fill the table by range length, so each smaller range is ready before a bigger range uses it.
- The brute force over all orders is only useful for checking small rows, because the number of orders grows as n!.