Redirecting to
NADOS


  Prev   Next

Burst Balloons







The only way to learn a new programming language is by writing programs in it.
- Dennis Ritchie.

Burst Balloons

Welcome Back Reader! In this article we will discuss about the next problem based on "Dynamic Programming" i.e. "Burst Balloons".

Prerequisite of this problem is Matrix Chain Multiplication, so that you can have a better idea of the Gap Strategy used in this problem.

Before you move any further, it is advised that you give this problem a fair try.

Let's jump to the problem. The video version of the problem is attached below.

Important Video : Problem Link, Solution Video

Understanding the problem

In this problem you are given an array of length N which represents N number of balloons. Each balloon is painted with a number on it.

If you burst a balloon with index i, you will get (arr[i-1] * arr[i] * arr[i+1]) number of coins. If arr[i-1] and arr[i+1] don't exist, then you may assume their value as 1.

All you have to do is collect the maximum coins by bursting all the balloons.

For Example
Sample Input: 3
1 2 3
Sample Output: 12.

How?

img
  • There are 6 possible orders in which 3 balloons (painted as 1 2 3) can be burst. So in the figure we have explored all these orders. Let's talk about one of them; (2 -> 3 -> 1).
  • Order (2 -> 3 -> 1) implies that among the given balloons (1 2 3), the balloon painted with 2 is burst first. So the number of coins collected will be (1*2*3 = 6).
  • Then the balloon painted with 3 is burst among the balloons left (1 3). So the number of coins collected will be (1*3*1 = 3).
  • Then the balloon painted with 1 is burst among the balloons left (1). So the number of coins collected will be (1*1 *1= 1).
  • Therefore the total coins collected would be (6 + 3 + 1 = 10).

For more clarity of the question, watch the following part of the video.

Approach
Moving On
  • In order to solve this problem we will use the Gap Strategy of dynamic programming.
    • In this strategy we use a 2D array of n x n and then we assign some meaning to the cells of the 2D array.
    • Then we fill the matrix diagonally, moving from smaller problems to bigger problems.
  • Let's consider another example; array = {2, 3, 1, 5, 6, 4 }. Before moving to building dp matrix; take a look at the recursion tree given below:
    • img
  • In this tree diagram, we have explored all the ways considering that for any value, say 1, the left (2, 3) and the right (5, 6, 4) of it have already managed to burst in such a way that they produce the maximum number of coins.
  • Now we are left with only 1 balloon painted and we have only one way to burst this balloon. And bursting this balloon will only contribute the value (1) number of coins to the answer.
  • We consider all such cases (i.e. corresponding to each balloon) and at last the case which gives the maximum answer is also the answer for the problem.
  • This problem can be solved using recursion as well but that wouldn't be an efficient way to do it because of repeating sub-problems. That's why we will use dynamic programming's gap strategy to solve this.

    • For more clarity of the above part, watch the following part of the video.

  • Now let's draw the dp for this example.
    • img
  • As always we assign some meaning to the cell of this dp matrix and the lower triangular part of this dp is meaningless.
  • Each cell stores the value of the maximum number of coins collected to burst the balloons corresponding to the sub-array to which the cell corresponds.
  • And each cell, dp[i][j] corresponds to a sub-array which starts from index i and ends at index j in the input array.
  • Like at dp[1][3], the cell will store the value of the maximum number of coins collected to burst the balloons corresponding to the sub-array {3, 1, 5, 6}.
  • For gap = 0; in this diagonal (i = j) which means there is only one value in the sub-array. And to burst only one balloon, we know the rule (given in the question) that we need to multiply the value of this balloon (at index i) with the values of the balloon in the left and in the right of the particular balloon.
  • Like at dp[2][2] the value to be stored will be (3(left value) * 1 * 5 (right value) = 15).
  • And in case, if the balloon has no other balloon either in the right or in the left then considers the right or left value as 1.
  • Like at dp[0][0] the value to be stored will be (1(no left value so using 1) * 2 * 3 (right value) = 6).
  • Using the above rules, we fill the rest of the diagonal (gap = 0).
    • img
  • Then we move to the next diagonal and fill it (gap = 1). In this diagonal, the length of the subarray is 2. That means we need to fill this diagonal with the value of the maximum number of coins collected to burst 2 balloons.
  • To burst two balloons we have two options; we can either burst the first balloon first or the second balloon first.
    • img
  • Consider the first cell of this diagonal; this cell i.e. dp[0][1] corresponds to the {2, 3} sub-array. So we can either burst the balloon painted 2 first or balloon painted 3 first.
  • If we burst the balloon painted 2 first then the number of coins collected will be (1 (no left value; use 1) *2*3 (right value) = 6).
  • After that the balloon painted with 3 is burst among the balloons left. So the number of coins collected will be (1(no left value; use 1) *3*1 (right value) = 3).
  • Therefore the total coins collected would be (6 + 3 = 9).
  • If we burst the balloon painted 3 first then the number of coins collected will be (2 (left value) *3*1 (right value) = 6).
  • After that the balloon painted with 2 is burst among the balloons left. So the number of coins collected will be (1(no left value; use 1) *2*1 (right value) = 2).
  • Therefore the total coins collected would be (6 + 2 = 8).
  • Then we compare these values and find that 9 is the maximum value. Therefore we store 9 at dp[0][1]. In the similar way we fill the rest of this diagonal.

    • For more clarity of the above part, watch the following part of the video.

  • This manual way of filling the matrix is lengthy and takes a lot of time so let's try to build the generic solution.
  • To build the generic solution consider the cell, dp[1][4] which corresponds to {3, 1, 5, 6}.
    • img
  • We explore all the possibilities to get the maximum score. First way can be if we burst 3 at last, then we can get the value for bursting {1, 5, 6} from the dp which will be stored at dp[2][4] and there is no left in this case.
  • And apart from {3, 1, 5, 6} there is only {2, 4} left in the array and if 3 is to be burst at last then we will have {2, 3, 4} left in the array and we can calculate the value for bursting 3 from this information; which will be (2 * 3 * 4). For the result we add both these values (dp[2][4] +(2 * 3 * 4)).
  • Let's discuss one more case for better clarity.
  • If we decide to burst 5 at last, then we can get the value for bursting the left part {3, 1} from the dp which is stored at dp[1][2] and the value for bursting the right part {6} which is stored at dp[4][4].
  • And apart from {3, 1, 5, 6} there is only {2, 4} left in the array and if 5 is to be burst at last then we will have {2, 5, 4} left in the array and we can calculate the value for bursting 5 from this information; which will be (2 * 5 * 4).
  • For the result we add all these values (dp[1][2] + dp][4][4] +(2 * 3 * 4)).
  • Similarly we can explore other ways also.
    • img
  • Similarly we explore all the possibilities for {2, 3, 1, 5} and {1, 5, 6, 4}.
    • img
    img
  • Now take a look at the sub-array {3, 1, 5, 6} once again.
  • At this point we can generalize a formula to calculate the score when a specific value in any sub-array like if 1in {3, 1, 5, 6} is burst last. Using this formula we can then calculate the score for each value if that value's balloon burst last in {3, 1, 5, 6}. And store the value with maximum score in the cell dp[1][4] which corresponds to {3, 1, 5, 6}.
  • We can vary a for loop with k to explore each case. K varies from i to j, I being the starting index of subarray and j being the ending index of subarray.
  • While calculating the score using the generic formula we need to take care of certain things. If there is no left part of the kth value in the subarray then we add 0 in that case instead of dp[i][k-1].
  • Similarly we handle the right part. If there is no right part of the kth value in the subarray then we add 0 in that case instead of dp[k+1][j].
  • Then to calculate the coins for bursting that kth value of the subarray; if the subarray includes the first element of the array then we use 1 as the left value for multiplying with the present value (kth).
  • And if the subarray includes the last element of the array then we use 1 as the right value for multiplying with the present value (kth).

    • For more clarity of the above part, watch the following part of the video.

import java.io.*; import java.util.*; public class Main { public static void main(String[] args) { Scanner scn = new Scanner(System.in); int n = scn.nextInt(); int[] arr = new int[n]; for (int i = 0; i < arr.length; i++) { arr[i] = scn.nextInt(); } System.out.println(solution1(arr)); } public static int solution1(int[] arr) { if (arr.length == 0) { //1 return 0; } int[][] dp = new int[arr.length][arr.length]; //2 for (int gap = 0; gap < arr.length; gap) { //3 int si = 0, ei = gap; //4 while (ei < arr.length) { //5 for (int k = si; k <= ei; k++) { //6 int leftVal = 1; int rightVal = 1; if (si != 0) { //7 leftVal = arr[si - 1]; } if (ei != arr.length - 1) { //8 rightVal = arr[ei + 1]; } int before = 0; //9 int after = 0; if (si != k) { //10 before = dp[si][k - 1]; } if (ei != k) { //11 after = dp[k + 1][ei]; } dp[si][ei] = Math.max(dp[si][ei], before + after + (leftVal * rightVal * arr[k])); //12 } si++; //13 ei++; } } return dp[0][arr.length - 1]; //14 } }
java; true";

Explanation of the code (with respect to comment numbers)

  1. To start with, we check if the input array is empty, if yes then we return 0.
  2. Otherwise we make a dp of size n x n, n being input array's length.
  3. After that we run a for loop initializing a variable gap to 0 until this gap remains less than n; to fill this dp matrix diagonally.
  4. Inside this for loop we define two variables si (starting index) to 0 and ei (ending index) to gap.
  5. Now we use a nested while loop to fill the diagonal corresponding to the gap value until the ei remains less than n.
  6. Then inside the nested while loop we use a for loop initializing k to si to ei; to explore all the cases for subarray from si to ei to get the maximum score. And on entering this loop we initialize two more variables leftval and rightval to 1 (default for further use).
  7. Then we check if si is not equal to 0 and if it isn't equal then we update the leftval to arr[si-1].
  8. Then we check if ei is not equal to n (array.length) and if it isn't equal then we update the rightval to arr[ei+1].
  9. We initialize two more variables before and after to 0 (default for further use).
  10. Then we check if si is not equal to k and if it isn't equal then we update the before to dp[si][k-1].
  11. Then we check if ei is not equal to k and if it isn't equal then we update the after to dp[k+1][ei].
  12. Then we calculate the score corresponding to the present k and then update the dp[si][ei] if the new score is greater than the previous score present at dp[si][ei]. We do this using the Math.max function.
  13. Then we come out of the for loop (of k) and enter the while loop once again. Here we increment the si and ei by 1 so that we can fill the next cell of the same diagonal in the next iteration of the while loop.
  14. After coming out of the for loop (of gap); it means we have completely filled the dp matrix and the result will be present at dp[0][array.length]. So at last we return this value.

For more clarity of the code, watch the following part of the video.

Analysis
Time Complexity: O(n^3)

A for loop, a nested while loop and then again a nested for loop; which condenses to O(n^3).

Space Complexity: O(n^2)

One n x n sized 2D array is used which consumes the space of order O(n^2).

  • We hope that this article was helpful. If somehow you are finding it difficult to understand this problem there is the always the video lecture to help you out.
  • You can contact us via our website. Doubts, suggestions and feedback are always welcomed.
  • It is also advised that you follow the sequence of modules and questions which is there on our website.
  • Keep practicing more and more problems daily. Meditate enough on each step of each problem.

All the best for an exciting future!
Happy Coding!

Author: Nikita Aggarwal
 
Run
Id Name