312. Burst Balloons – Leetcode Solutions

Example 1:

Input: nums = [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

Example 2:

Input: nums = [1,5]
Output: 10

class Solution:
    def maxCoins(self, nums: List[int]) -> int:
        # Add 1 at the beginning and the end of the list to handle edge cases easily.
        nums = [1] + nums + [1]
        n = len(nums)
        
        # Create a dp array where dp[left][right] represents the maximum coins
        # that can be obtained by bursting all balloons between indices left and right (exclusive).
        dp = [[0] * n for _ in range(n)]
        
        # Iterate over the possible lengths of subarrays to burst
        for length in range(2, n):  # length is the distance between 'left' and 'right'
            for left in range(0, n - length):  # left boundary of the subarray
                right = left + length  # right boundary of the subarray
                
                # Iterate over each balloon to burst last in this subarray (between left and right)
                for i in range(left + 1, right):
                    # Calculate the coins gained by bursting the ith balloon last in this range
                    coins = nums[left] * nums[i] * nums[right]
                    
                    # Add the coins gained from the subproblems (left, i) and (i, right)
                    coins += dp[left][i] + dp[i][right]
                    
                    # Update the dp value for the range (left, right)
                    dp[left][right] = max(dp[left][right], coins)
        
        # Return the result from bursting all balloons between the first and last added 1s
        return dp[0][n - 1]

class Solution {
public:
    int maxCoins(vector<int>& nums) {
        // Add 1 at the beginning and the end of the nums array to handle boundary conditions easily
        nums.insert(nums.begin(), 1);
        nums.push_back(1);
        
        int n = nums.size();  // n is the size of the modified nums array
        
        // Create a 2D dp array where dp[left][right] will store the maximum coins
        // we can get by bursting all the balloons between the indices left and right (exclusive)
        vector<vector<int>> dp(n, vector<int>(n, 0));
        
        // Iterate over the possible lengths of subarrays to burst
        for (int length = 2; length < n; ++length) {
            for (int left = 0; left < n - length; ++left) {
                int right = left + length;  // Define the right boundary of the subarray
                
                // Iterate over each balloon to burst last in the range (left, right)
                for (int i = left + 1; i < right; ++i) {
                    // Calculate the coins gained by bursting the ith balloon last in this range
                    int coins = nums[left] * nums[i] * nums[right];
                    
                    // Add the coins obtained from the two subproblems dp[left][i] and dp[i][right]
                    coins += dp[left][i] + dp[i][right];
                    
                    // Update the dp array with the maximum coins for the range (left, right)
                    dp[left][right] = max(dp[left][right], coins);
                }
            }
        }
        
        // The result is stored in dp[0][n-1], which corresponds to bursting all balloons
        // between the first and last added 1s (i.e., the entire original nums array)
        return dp[0][n-1];
    }
};

var maxCoins = function(nums) {
    // Add 1 at the beginning and the end of the nums array to simplify boundary conditions
    nums.unshift(1);
    nums.push(1);
    
    const n = nums.length;  // n is the size of the modified nums array
    
    // Create a 2D dp array where dp[left][right] will store the maximum coins
    // we can get by bursting all balloons between the indices left and right (exclusive)
    const dp = Array.from({ length: n }, () => Array(n).fill(0));
    
    // Iterate over the possible lengths of subarrays to burst
    for (let length = 2; length < n; length++) {
        for (let left = 0; left < n - length; left++) {
            let right = left + length;  // Define the right boundary of the subarray
            
            // Iterate over each balloon to burst last in the range (left, right)
            for (let i = left + 1; i < right; i++) {
                // Calculate the coins gained by bursting the ith balloon last in this range
                const coins = nums[left] * nums[i] * nums[right];
                
                // Add the coins obtained from the two subproblems dp[left][i] and dp[i][right]
                const totalCoins = coins + dp[left][i] + dp[i][right];
                
                // Update the dp array with the maximum coins for the range (left, right)
                dp[left][right] = Math.max(dp[left][right], totalCoins);
            }
        }
    }
    
    // The result is stored in dp[0][n-1], which corresponds to bursting all balloons
    // between the first and last added 1s (i.e., the entire original nums array)
    return dp[0][n - 1];
};

class Solution {
    public int maxCoins(int[] nums) {
        // Create a new array with 1 added at the beginning and the end of nums
        int n = nums.length;
        int[] extendedNums = new int[n + 2];
        
        // Add 1 at the beginning and the end of the extendedNums array
        extendedNums[0] = 1;
        extendedNums[n + 1] = 1;
        
        // Copy the original nums array into extendedNums
        for (int i = 1; i <= n; i++) {
            extendedNums[i] = nums[i - 1];
        }
        
        // Create a dp array where dp[left][right] represents the maximum coins
        // we can collect by bursting all balloons between indices left and right (exclusive)
        int[][] dp = new int[n + 2][n + 2];
        
        // Iterate over possible lengths of subarrays
        for (int length = 2; length < n + 2; length++) {
            for (int left = 0; left < n + 2 - length; left++) {
                int right = left + length;  // Define the right boundary of the subarray
                
                // Iterate over each balloon to burst last in this subarray (between left and right)
                for (int i = left + 1; i < right; i++) {
                    // Calculate the coins obtained by bursting the ith balloon last in this subarray
                    int coins = extendedNums[left] * extendedNums[i] * extendedNums[right];
                    
                    // Add the coins obtained from the two subproblems: dp[left][i] and dp[i][right]
                    coins += dp[left][i] + dp[i][right];
                    
                    // Update the dp value for the range (left, right)
                    dp[left][right] = Math.max(dp[left][right], coins);
                }
            }
        }
        
        // The result is stored in dp[0][n+1], which corresponds to bursting all balloons
        // between the first and last added 1s (i.e., the entire original nums array)
        return dp[0][n + 1];
    }
}