Solution For Burst Balloons

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.

Step by Step Implementation For Burst Balloons

class Solution {
    public int maxCoins(int[] nums) {
        // Base case
        if (nums == null || nums.length == 0) {
            return 0;
        }
        
        // General case
        int n = nums.length;
        int[][] dp = new int[n][n];
        
        for (int len = 1; len <= n; len++) {
            for (int i = 0; i <= n - len; i++) {
                int j = i + len - 1;
                for (int k = i; k <= j; k++) {
                    // leftValue/rightValue is initially 1
                    int leftValue = 1;
                    int rightValue = 1;
                    
                    if (i != 0) {
                        leftValue = nums[i-1];
                    }
                    if (j != n - 1) {
                        rightValue = nums[j+1];
                    }
                    
                    // before is initially 0
                    int before = 0;
                    if (i != k) {
                        before = dp[i][k-1];
                    }
                    
                    // after is initially 0
                    int after = 0;
                    if (j != k) {
                        after = dp[k+1][j];
                    }
                    
                    dp[i][j] = Math.max(dp[i][j], before + after + leftValue * nums[k] * rightValue);
                }
            }
        }
        
        return dp[0][n - 1];
    }
}

def maxCoins(self, nums: List[int]) -> int:
    # Base case
    if len(nums) == 0:
        return 0
    
    # Recursive case
    max_coins = 0
    for i in range(len(nums)):
        # Burst the balloon at index i
        left = nums[:i]
        right = nums[i+1:]
        
        # Calculate the coins we get from bursting this balloon
        coins = nums[i] * (1 if len(left) == 0 else max(left)) * (1 if len(right) == 0 else max(right))
        
        # Add the coins from the subproblems
        coins += self.maxCoins(left)
        coins += self.maxCoins(right)
        
        # Update the maximum number of coins
        max_coins = max(coins, max_coins)
        
    return max_coins

var maxCoins = function(nums) {
    // Base case: if nums is empty, there are no coins to burst
    if (nums.length === 0) {
        return 0;
    }
    
    // Initialize a 2D array to store the maximum number of coins
    // that can be obtained by bursting balloons from i to j
    const dp = new Array(nums.length).fill(0).map(() => new Array(nums.length).fill(0));
    
    // Consider bursting balloons from i to j, where j >= i
    for (let j = 0; j < nums.length; j++) {
        for (let i = j; i >= 0; i--) {
            // Consider bursting balloons from i to j, where k is the last balloon to burst
            for (let k = i; k <= j; k++) {
                // The number of coins obtained by bursting balloon k
                // is nums[i - 1] * nums[k] * nums[j + 1], where i - 1 and j + 1
                // represent the balloons on the left and right of balloon k
                // that have not been burst yet
                const coins = ((i === 0) ? 1 : nums[i - 1]) * nums[k] * ((j === nums.length - 1) ? 1 : nums[j + 1]);
                
                // The maximum number of coins that can be obtained by
                // bursting balloons from i to j is the maximum of the following:
                // 1. The maximum number of coins that can be obtained by
                //    bursting balloons from i to j without balloon k
                // 2. The maximum number of coins that can be obtained by
                //    bursting balloons from i to k - 1 and from k + 1 to j
                //    and then bursting balloon k
                dp[i][j] = Math.max(dp[i][j], ((k === i) ? 0 : dp[i][k - 1]) + ((k === j) ? 0 : dp[k + 1][j]) + coins);
            }
        }
    }
    
    // Return the maximum number of coins that can be obtained by
    // bursting all balloons
    return dp[0][nums.length - 1];
};

int maxCoins(vector& nums) {
    int n = nums.size();
    nums.insert(nums.begin(), 1);
    nums.push_back(1);
    vector> dp(nums.size(), vector(nums.size(), 0));
    for (int len = 1; len <= n; ++len) {
        for (int i = 1; i <= n - len + 1; ++i) {
            int j = i + len - 1;
            for (int k = i; k <= j; ++k) {
                dp[i][j] = max(dp[i][j], dp[i][k - 1] + dp[k + 1][j] + nums[i - 1] * nums[k] * nums[j + 1]);
            }
        }
    }
    return dp[1][n];
}

This solution uses a dynamic programming approach to solve the problem. The idea is to keep track of the maximum number of balloons that can be burst at each index i, and to update this value as we process each index from left to right.

We can do this by maintaining an array maxValues, where maxValues[i] represents the maximum number of balloons that can be burst at index i. To calculate the value at each index, we need to consider all the possible ways of bursting the balloons before and after index i.

For each index j before i, we can calculate the number of balloons that can be burst by bursting the balloon at index i and then all the balloons between j and i. Similarly, for each index k after i, we can calculate the number of balloons that can be burst by bursting the balloon at index i and then all the balloons between i and k.

The total number of balloons that can be burst at index i is then the sum of these two values, plus the value of the balloon at index i.

We can use this approach to fill in the entire array maxValues, and the maximum number of balloons that can be burst is the last element in maxValues.

public int MaxCoins(int[] nums) { int[] maxValues = new int[nums.Length]; for (int i = 0; i < nums.Length; i++) { // consider all indices j before i int j = i - 1; while (j >= 0) { // consider all indices k after i int k = i + 1; while (k < nums.Length) { // calculate the number of balloons that can be burst by // bursting the balloon at index i and then all the // balloons between j and i int leftValue = nums[i] * nums[j]; if (j != 0) { leftValue *= nums[j - 1]; } // calculate the number of balloons that can be burst by // bursting the balloon at index i and then all the // balloons between i and k int rightValue = nums[i] * nums[k]; if (k != nums.Length - 1) { rightValue *= nums[k + 1]; } // update the maximum number of balloons that can be // burst at index i maxValues[i] = Math.Max(maxValues[i], leftValue + rightValue); k++; } j--; } } return maxValues[nums.Length - 1]; }