Burst Balloons

                                            
class Solution {
public:
    int maxCoins(vector<int>& nums) {
        int n = nums.size();
        nums.insert(nums.begin(), 1);
        nums.push_back(1);
        
        vector<vector<int>> dp(n + 2, vector<int>(n + 2, 0));
        
        for (int len = 1; len <= n; ++len) {
            for (int left = 1; left <= n - len + 1; ++left) {
                int right = left + len - 1;
                for (int k = left; k <= right; ++k) {
                    dp[left][right] = max(dp[left][right], dp[left][k - 1] + nums[left - 1] * nums[k] * nums[right + 1] + dp[k + 1][right]);
                }
            }
        }
        
        return dp[1][n];
    }
};

                                            
class Solution {
    public int maxCoins(int[] nums) {
        int n = nums.length;
        int[] newNums = new int[n + 2];
        newNums[0] = 1;
        newNums[n + 1] = 1;
        for (int i = 1; i <= n; i++) {
            newNums[i] = nums[i - 1];
        }
        
        int[][] dp = new int[n + 2][n + 2];
        for (int len = 1; len <= n; len++) {
            for (int left = 1; left <= n - len + 1; left++) {
                int right = left + len - 1;
                for (int k = left; k <= right; k++) {
                    dp[left][right] = Math.max(dp[left][right], dp[left][k - 1] + newNums[left - 1] * newNums[k] * newNums[right + 1] + dp[k + 1][right]);
                }
            }
        }
        
        return dp[1][n];
    }
}

                                            
class Solution(object):
    def maxCoins(self, nums):
        n = len(nums)
        nums = [1] + nums + [1]
        dp = [[0] * (n + 2) for _ in range(n + 2)]
        
        for length in range(1, n + 1):
            for i in range(1, n - length + 2):
                j = i + length - 1
                for k in range(i, j + 1):
                    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]

                                            
int maxCoins(int* nums, int numsSize) {
    int n = numsSize;
    int* coins = (int*)calloc(n + 2, sizeof(int));
    coins[0] = coins[n+1] = 1;
    for (int i = 1; i <= n; i++) {
        coins[i] = nums[i - 1];
    }
    
    int dp[n + 2][n + 2];
    memset(dp, 0, sizeof(dp));
    for (int len = 3; len <= n + 2; len++) {
        for (int left = 0; left <= n + 2 - len; left++) {
            int right = left + len - 1;
            for (int k = left + 1; k < right; k++) {
                dp[left][right] = fmax(dp[left][right], dp[left][k] + dp[k][right] + coins[left] * coins[k] * coins[right]);
            }
        }
    }
    
    return dp[0][n+1];
}

                                            
public class Solution {
    public int MaxCoins(int[] nums) {
        int n = nums.Length;
        int[] newNums = new int[n + 2];
        newNums[0] = 1;
        newNums[n + 1] = 1;
        
        for (int i = 0; i < n; i++) {
            newNums[i + 1] = nums[i];
        }
        
        int[,] dp = new int[n + 2, n + 2];
        
        for (int len = 1; len <= n; len++) {
            for (int left = 1; left <= n - len + 1; left++) {
                int right = left + len - 1;
                for (int k = left; k <= right; k++) {
                    dp[left, right] = Math.Max(dp[left, right], 
                                               newNums[left - 1] * newNums[k] * newNums[right + 1] + dp[left, k - 1] + dp[k + 1, right]);
                }
            }
        }
        
        return dp[1, n];
    }
}

                                            
/**
 * @param {number[]} nums
 * @return {number}
 */
var maxCoins = function(nums) {
    const n = nums.length;
    
    // Extend nums array with 1 at start and end
    const newNums = [1, ...nums, 1];
    
    // Initialize a 2D DP array with dimensions n+2 x n+2
    const dp = new Array(n+2).fill(0).map(() => new Array(n+2).fill(0));
    
    // Iterate over the range of each subarray length
    for (let len = 1; len <= n; len++) {
        for (let left = 1; left <= n - len + 1; left++) {
            // Calculate the right index of the subarray
            const right = left + len - 1;
            // Iterate over possible last balloon to burst in subarray
            for (let k = left; k <= right; k++) {
                // Update the maximum coins by bursting balloons wisely
                dp[left][right] = Math.max(dp[left][right], dp[left][k-1] + newNums[left-1] * newNums[k] * newNums[right+1] + dp[k+1][right]);
            }
        }
    }
    
    return dp[1][n];
};

                                            
function maxCoins(nums: number[]): number {
    const n = nums.length;
    const dp: number[][] = new Array(n + 2).fill(0).map(() => new Array(n + 2).fill(0));
    
    nums.unshift(1);
    nums.push(1);
    
    for (let len = 1; len <= n; len++) {
        for (let i = 1; i <= n - len + 1; i++) {
            const j = i + len - 1;
            for (let k = i; k <= j; k++) {
                dp[i][j] = Math.max(dp[i][j], dp[i][k - 1] + nums[i - 1] * nums[k] * nums[j + 1] + dp[k + 1][j]);
            }
        }
    }
    
    return dp[1][n];
};

                                            
class Solution {
    /**
     * @param Integer[] $nums
     * @return Integer
     */
    function maxCoins($nums) {
        $n = count($nums);
        $nums = array_merge([1], $nums, [1]);
        
        $dp = array_fill(0, $n + 2, array_fill(0, $n + 2, 0));
        
        for ($len = 1; $len <= $n; $len++) {
            for ($left = 1; $left <= $n - $len + 1; $left++) {
                $right = $left + $len - 1;
                for ($k = $left; $k <= $right; $k++) {
                    $dp[$left][$right] = max($dp[$left][$right], $nums[$left - 1] * $nums[$k] * $nums[$right + 1] + $dp[$left][$k - 1] + $dp[$k + 1][$right]);
                }
            }
        }
        
        return $dp[1][$n];
    }
}

                                            
class Solution {
    func maxCoins(_ nums: [Int]) -> Int {
        let n = nums.count
        var dp = Array(repeating: Array(repeating: 0, count: n+2), count: n+2)
        let balloons = [1] + nums + [1]
        
        for len in 1...n {
            for i in 1...(n-len+1) {
                let j = i + len - 1
                for k in i...j {
                    dp[i][j] = max(dp[i][j], dp[i][k-1] + balloons[i-1]*balloons[k]*balloons[j+1] + dp[k+1][j])
                }
            }
        }
        
        return dp[1][n]
    }
}

                                            
class Solution {
    fun maxCoins(nums: IntArray): Int {
        val n = nums.size
        val newNums = IntArray(n + 2)
        newNums[0] = 1
        newNums[n + 1] = 1
        for (i in 1..n) {
            newNums[i] = nums[i - 1]
        }

        val dp = Array(n + 2) { IntArray(n + 2) }
        for (length in 1..n) {
            for (left in 1..n - length + 1) {
                val right = left + length - 1
                for (last in left..right) {
                    dp[left][right] = maxOf(dp[left][right],
                        newNums[left - 1] * newNums[last] * newNums[right + 1] +
                                dp[left][last - 1] + dp[last + 1][right]
                    )
                }
            }
        }

        return dp[1][n]
    }
}

                                            
class Solution {
  int maxCoins(List<int> nums) {
    int n = nums.length;
    nums.insert(0, 1);
    nums.add(1);

    List<List<int>> dp = List.generate(n + 2, (_) => List.filled(n + 2, 0));

    for (int len = 1; len <= n; len++) {
      for (int left = 1; left <= n - len + 1; left++) {
        int right = left + len - 1;
        for (int k = left; k <= right; k++) {
          dp[left][right] = 
            dp[left][right] = dp[left][right] > (dp[left][k - 1] + nums[left - 1] * nums[k] * nums[right + 1] + dp[k + 1][right]) ? dp[left][right] : (dp[left][k - 1] + nums[left - 1] * nums[k] * nums[right + 1] + dp[k + 1][right]);
        }
      }
    }

    return dp[1][n];
  }
}

                                            
func maxCoins(nums []int) int {
    n := len(nums)
    dp := make([][]int, n+2)
    for i := 0; i < n+2; i++ {
        dp[i] = make([]int, n+2)
    }

    newNums := make([]int, n+2)
    newNums[0], newNums[n+1] = 1, 1
    for i := 1; i <= n; i++ {
        newNums[i] = nums[i-1]
    }

    for length := 1; length <= n; length++ {
        for left := 1; left <= n-length+1; left++ {
            right := left + length - 1
            for k := left; k <= right; k++ {
                dp[left][right] = max(dp[left][right], dp[left][k-1]+dp[k+1][right]+newNums[left-1]*newNums[k]*newNums[right+1])
            }
        }
    }

    return dp[1][n]
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

                                            
# @param {Integer[]} nums
# @return {Integer}
def max_coins(nums)
    n = nums.length
    nums.unshift(1)
    nums.push(1)
    dp = Array.new(n+2) { Array.new(n+2, 0) }
    
    (1..n).each do |len|
        (1..n-len+1).each do |left|
            right = left + len - 1
            (left..right).each do |i|
                dp[left][right] = [dp[left][right], nums[left-1] * nums[i] * nums[right+1] + dp[left][i-1] + dp[i+1][right]].max
            end
        end
    end
    
    dp[1][n]
end

To solve this coding challenge, you need to use a dynamic programming approach to compute the maximum number of coins you can collect by strategically bursting the balloons. This problem falls under the category of interval dynamic programming, where you solve smaller sub-problems and use those solutions to build up the answer to the overall problem.

Explanation

Key steps include adding virtual balloons with value

1

at both ends of the array to handle boundary conditions easily. After that, we create a dynamic programming (DP) table where

dp[i][j]

represents the maximum coins obtainable by bursting all balloons between index

i

and

j

(both inclusive). We will iterate over different lengths of sub-arrays, and for each sub-array, we will try bursting each balloon as the last one in that sub-array. The DP table is updated based on the best choice of the balloon to burst last in each sub-array.

Initial Setup : Extend the array by adding
1

at both ends.
DP Table Initialization : Create a table
dp

where
dp[i][j]

stores the maximum coins that can be collected by bursting all balloons in the range
[i, j]

.
Filling the DP Table : Iterate over all possible sub-array lengths. For each sub-array, consider every possible position for the last balloon to burst and calculate the number of coins gained. Update the DP table accordingly.
Result : Finally, the DP entry
dp[1][n]

, which considers the entire range excluding the virtual balloons, will have the result.

This problem involves filling a DP table iteratively based on previously computed values.

Pseudocode with Comments

                                            
# Step to solve the problem
function maxCoins(nums):
    # Add virtual balloons with value 1 at both ends to handle boundaries
    nums = [1] + nums + [1]
    
    # Obtain the length of the modified nums array
    n = length(nums)
    
    # Initialize the DP table with zeros
    dp = create 2D array of size n x n filled with 0
    
    # Iterate over sub-array lengths starting from 1 up to the length of the original nums
    for length from 1 to original_length of nums:
        
        # Iterate over all possible starting points for sub-arrays of given length
        for i from 1 to n - length:
            # Determine the ending point of the sub-array
            j = i + length - 1
            
            # Try bursting each balloon in this sub-array as the last balloon
            for k from i to j:
                # coins gained by bursting the k-th balloon last
                coins = nums[i-1] * nums[k] * nums[j+1]
                
                # Total coins for this sub-array, including the best results from
                # sub-problems to the left and right of k
                total_coins = dp[i][k-1] + coins + dp[k+1][j]
                
                # Update the DP table entry with the maximum coins collected so far
                dp[i][j] = max(dp[i][j], total_coins)
    
    # The final result is stored in dp[1][n-2], which ignores the virtual balloons
    return dp[1][n-2]

# Call the function
# Example 1: maxCoins([3,1,5,8]) should return 167
# Example 2: maxCoins([1,5]) should return 10

Detailed Steps in Pseudocode

Define the
maxCoins

function : This function starts by adding virtual balloons with value
1

at the beginning and end of the
nums

array to handle boundary conditions effortlessly.
Modify the array : Append
1

at both ends of the
nums

array to facilitate easier multiplication without out-of-bound issues.
Initialize the DP table : Create a 2D list
dp

initialized to zero, which will store the maximum coins obtained for every possible range
[i, j]

.
Iterate over all possible lengths of the sub-array : For every possible sub-array length from
1

to
n

, iterate over all possible starting indices
i

of the sub-array.
Determine the end index
j

: For each starting index
i

, determine the ending index
j

of the sub-array based on the current length.
Iterate over all possible last bursts : For each sub-array
[i, j]

, iterate over all possible balloons
k

which can be the last one to be burst.
Calculate coins obtained : For each balloon
k

, calculate the coins obtained by bursting it last within the sub-array
[i, j]

considering the product of adjacent balloons (accounting for the newly added virtual balloons).
Update the DP table : Update
dp[i][j]

with the maximum coins obtained so far, by considering both previously computed sub-problems (
dp[i][k-1]

and
dp[k+1][j]

).
Return the result : After completing the DP table, the result will be in
dp[1][n-2]

, which corresponds to the maximum coins collected by bursting all balloons in the original
nums

array.

This detailed, iterative process ensures that we optimally compute the maximum coins collectible by bursting the balloons in the best possible sequence.