Burst Balloons
I'd like to discuss today a new problem called the "Burst Balloons" problem.
This is an interesting problem because it challenges us to rethink our hypothesis and strengthen it.
In this problem, we are given a set of balloons with numbers on them. The numbers represent the cost of each balloon. If we pop a balloon i, we get coins by the following formula: B[i - 1]*B[i]*B[i + 1].
Where B[i] represents the cost of balloon i and B[i + 1], B[i - 1] the corresponding costs of the right and left balloons to the ith balloon.
For the sake of this problem, we may assume that B[-1] and B[N + 1] (N = the last balloon) are both 1. The problem asks you to maximize your profit by popping the balloons.
Notice however, that once you pop a balloon i, balloons i - 1 and i + 1 become neighbors of each other.
Let's try to solve this problem with induction:
P(n < N) - we know how to solve the problem for n < N balloons and get the max profit for them.
P(1) - The base case deals with only a single balloon, in which case the answer is straightforward - we just pop it and collect the coins for it.
P(N) - Assuming we have N balloons, how do we reduce the problem to smaller subproblems ? We have to pop one or more of the balloons to reduce the problem size. However, which balloon should we pop first ? This is tricky. When we pop a balloon we modify the rest of the system. Also,which one maximizes our profit ? At this point, we notice that we need to change our perspective.
What if instead of choosing a balloon to pop first, we actually choose a balloon to pop last ? so we reduce P(N) to P(N - 1) based on the last balloon to pop. This way, our subproblems are not affected by our decision. But which balloon should we save for last ? anyone of them may end up with a different cost. In such a case we are left with no choice but to try every one of them as the last balloon to pop and pick the one that maximizes our profit.
We'll solve this problem using dynamic programming. The recurrence relation is as follows:
D[i,j] = max{over all k: D[i,k - 1] + D[k + 1,j] + (B[i - 1] * B[k] * B[j + 1])}
notice how this recurrence relation maps to our hypothesis: D[i,j] represents P(N) and D[i,k -1],D[k + 1,j] represent our hypothesis: P(n < N). We multiply B[k] (the last balloon to pop) with B[i - 1] and B[j + 1] because we assume that the rest of the balloons betwee i to k and between k to j have been popped already.
So now, writing the code should be straight forward:
