Burst Balloons - Leetcode Solution

Problem Description:

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.

Note:

You may imagine nums[-1] = nums[n] = 1. They are not real therefore you can not burst them. 0 ≤ n ≤ 500, 0 ≤ nums[ i ] ≤ 100

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:

One way to approach the problem is to use dynamic programming. The idea is to use a 2D array dp[i][j] which stores the maximum coins that can be obtained by bursting balloons from i to j.

The subproblem in this approach can be dividing the balloons array by determining the last balloon to be burst and calculating the coins obtained for this partition.

To calculate dp[i][j], we iterate over all possible balloons l that can be burst last in the range i to j. For this iteration, we need to take care of the subranges (i, l-1) and (l+1, j) to ensure that the partition is correct. The maximum coins that can be obtained for partition (i, j) by bursting balloon l is given by the formula:

dp[i][j] = max(dp[i][j], dp[i][l-1] + nums[i-1]*nums[l]*nums[j+1] + dp[l+1][j])

The base case for this approach is dp[i][i] = nums[i-1]*nums[i]*nums[i+1]. The answer to the problem is dp[1][n], where n is the length of balloons array nums.

The time complexity of the dynamic programming approach is O(n^3). The 2D array dp has a size of n x n, and for each cell dp[i][j], we need to iterate over all possible balloons l, resulting in n^3 time complexity. However, this approach can be optimized using Divide and Conquer or memoization methods.

1