312. Burst Balloons

This problem asks to find the maximum coins you can collect by bursting balloons wisely. Bursting a balloon at index i yields nums[i-1] * nums[i] * nums[i+1] coins, treating out-of-bounds indices as having a value of 1.

Solution: Dynamic Programming

The optimal solution uses dynamic programming. We can represent the subproblem as finding the maximum coins achievable by bursting balloons within a given range.

1. State Definition:

Let dp[i][j] represent the maximum coins obtainable by bursting balloons in the range [i, j] (inclusive). Note that i and j are indices into an augmented array.

2. Augmenting the Input:

To handle boundary conditions easily, we add 1 to both ends of the nums array. This simplifies the calculation of coins when bursting balloons near the edges.

3. Base Cases:

• dp[i][i] = 0 for all i: Bursting a single balloon yields no additional coins.
• dp[i][i+1] = 0 for all i: Bursting only two adjacent balloons will not generate any additional coins with the 1s added on both ends.

4. Recurrence Relation:

For a range [i, j], we consider each possible last balloon to burst k (where i < k < j). The maximum coins are obtained by bursting balloons in [i, k] and [k, j] independently, and then bursting k:

dp[i][j] = max(dp[i][j], dp[i][k] + dp[k][j] + arr[i] * arr[k] * arr[j])

where arr is the augmented array ([1] + nums + [1]).

5. Iteration Order:

To avoid issues with dependencies, we iterate through the dp array in a specific order:

• Outer loop iterates from larger ranges to smaller ranges (e.g., from j-i largest to smallest)
• Inner loop iterates through possible values of k.

6. Result:

The final answer is stored in dp[0][n+1], where n is the original length of nums.

Time and Space Complexity:

• Time Complexity: O(n³), due to the three nested loops in the dynamic programming solution.
• Space Complexity: O(n²), to store the dp table.

Code Implementation (Python):

class Solution:
    def maxCoins(self, nums: List[int]) -> int:
        n = len(nums)
        arr = [1] + nums + [1]  # Augment the array
        dp = [[0] * (n + 2) for _ in range(n + 2)]
 
        for length in range(2, n + 2):  # Iterate from smaller to larger lengths
            for i in range(n + 2 - length):
                j = i + length
                for k in range(i + 1, j):  # Iterate through possible last burst positions
                    dp[i][j] = max(dp[i][j], dp[i][k] + dp[k][j] + arr[i] * arr[k] * arr[j])
 
        return dp[0][n + 1]

The code in other languages (Java, C++, Go, TypeScript, Rust) follows the same logic and algorithmic approach, only differing in syntax. They all have the same time and space complexity.