Burst Balloon
Get started
জয় শ্রী রাম
🕉Problem Statement:
Given n balloons, indexed from 0 to n-1. Each balloon is painted with a number on it represented by array nums. You are asked to burst all the balloons. If the you burst balloon i you will get nums[left] * nums[i] * nums[right] coins. Here left and right are adjacent indices of i. After the burst, the left and right then becomes adjacent. Find the maximum coins you can collect by bursting the balloons wisely. You may imagine nums[-1] = nums[n] = 1. They are not real therefore you can not burst them.Example:
Input: [3,1,5,8] Output: 167 Explanation: nums = [3,1,5,8] --> [3,5,8] --> [3,8] --> [8] --> [] coins = 3*1*5 + 3*5*8 + 1*3*8 + 1*8*1 = 167
Solution:
If you think of bursting a balloon as multiplying two adjacent matrices, then this problem is exactly the classical DP problem Matrix-chain multiplication.For example, given [3,5,8] and bursting 5, the number of coins you get is the number of scalar multiplications you need to do to multiply two matrices A[3*5] and B[5*8]. So in this example, the original problem is actually the same as given a matrix chain A[1*3]*B[3*5]*C[5*8]*D[8*1], fully parenthesize it so that the total number of scalar multiplications is maximized, although the original matrix-chain multiplication problem asks to minimize it. Then you can see it clearly as a classical DP problem.
This problem is a great application for Dynamic Programming:All possible Cuts in all possible Intervals for the Last Operation concept. The Burst Balloon problem is seen as a difficult problem to solve by many, but when you really understand the core concepts and the classical problems so well that you can appreciate and fathom the versatility and potential of the classical problems ( Matrix Chain Multiplication in our case ) and understand the underlying concept, applications and common pattern of the problems, then as you see in this chapter the so-called difficult problems can be solved very easily. Often many of you look at others' solutions in website like Leetcode and think how the heck they came up with this elegant solution. Often times these elegant solutions come from deep and clear understanding of the the common classical problems and the core concepts.
As discussed in Dynamic Programming:All possible Cuts in all possible Intervals for the Last Operation , we will focus on the last operation. For this problem we will make each and every balloon the last balloon to be burst and take the one that gives the maximum value to us. We do this in bottom-up approach using tabulation, going from lower length of sub-problem to all the way up to the length of the original problem (len = 1 to N, where N = length of the original problem) leveraging the Dynamic Programming properties: Optimal Sub-structures and Overlapping Subproblems.
Java Code:
class Solution {
public int burstBalloons(int[] nums) {
if (nums.length == 0) {
return 0;
}
// Category of DP: making CUTS at all possible places (creating shorter intervals)
// In this problem, CUT = last balloon burst for a certain interval
// For every interval we will have to make every balloon as the
// last balloon burst in that interval and compute maxCoins for that
// interval.
// For an interval irrespective of which balloon is the last burst balloon
// we know what is going to be the nums[left] and nums[right].
// Since when we are talking about interval [beg, end] we set a rule
// that all other intervals remain intact (no balloons burst in any other intervals)
// nums[left] will be nums[beg - 1]
// and nums[right] will be nums[end + 1], (since this is the last
// balloon to be burst in this interval, there are no other balloons
// left in the current interval. So the two adjacent balloons
// at the boundary of the interval are the left and right balloons.)
// except for the entire interval (length = N, where N is length of nums)
// where nums[left] = 1 and nums[right] = 1 as
// there are are no balloons outside of the given nums[]
int totalBalloons = nums.length;
int[][] dp = new int[totalBalloons][totalBalloons];
for (int len = 1; len <= totalBalloons; len++) {
for (int beg = 0; beg <= totalBalloons - len; beg++) {
int end = beg + len - 1;
dp[beg][end] = Integer.MIN_VALUE;
for (int lastBalloonBurst = beg; lastBalloonBurst <= end; lastBalloonBurst++) {
int left = 1;
int right = 1;
int leftSum = 0;
int rightSum = 0;
if (beg > 0) {
left = nums[beg - 1];
}
if (end < totalBalloons - 1) {
right = nums[end + 1];
}
if (lastBalloonBurst != beg) {
leftSum = dp[beg][lastBalloonBurst - 1];
}
if (lastBalloonBurst != end) {
rightSum = dp[lastBalloonBurst + 1][end];
}
dp[beg][end] = Math.max(dp[beg][end], leftSum + (left * nums[lastBalloonBurst] * right) + rightSum);
}
}
}
return dp[0][totalBalloons - 1];
}
}
Python Code:
Login to Access Content
Time and Space Complexity:
Please subscribe to access the complexity analysis.
