Question

Burst Balloons

Intuition

While the ballons burst, it will not affect the score of another ballon, and the length of the list will always decrease. This means that we can use dynamic programming to solve this problem.

Approach

Consider a case, when $dp[i][j]$ means the maximum score you can get by bursting all the balloons between i and j. In this case, our answer would be $dp[0][n-1]$, if n is the length of the list.

Now, let’s figure out how to get $dp[i][j]$. As we mentioned in part Intuition, the length of the balloon is always decreasing, which means that we might be able to get $dp[i][j]$ by first counting a shorter interval, and the increase the interval to $0 \to n-1$.

Now, we have our solution:

First, we iterate the length of the interval.

Next, we can break the interval $i \to j$ into two sub intervals $i \to k-1$ and $k+1 \to j$.

Now we can compute the score of interval $i \to j$ by adding up sub intervals $i \to k-1$, $k + 1 \to j$, and burst the balloon k.

Because the balloons in sub interval $i \to k-1$ and $k + 1 \to j$ are already gone, so the score addition would be $nums[k] \times nums[i-1] \times nums[j+1]$.

The only thing we now need to consider is the edge of these subintervals. Knowing that the balloon we are now bursting can be the edge of the interval $i \to j$, meaning that we need to iterate $[i, j]$ inclusively.

Finally, you will get your result in $dp[0][n-1]$.

Complexity

  • Time complexity: $O(N^3)$. N is the length of the list.
  • Space complexity: $O(N^2)$. N is the length of the list.

Code

class Solution:
    def maxCoins(self, nums: List[int]) -> int:
        n = len(nums)
        nums = nums + [1]
        dp = [[0 for _ in range(n+1)] for _ in range(n+1)]

        for i in range(n):
            dp[i][i] = nums[i] * nums[i-1] * nums[i+1]

        for i in range(1, n):
            for l in range(n):
                if i + l == n:
                    break
                r = i + l
                for k in range(l, r+1):
                    dp[l][r] = max(dp[l][r], dp[l][k-1] + dp[k+1][r] + nums[k] * nums[l-1] * nums[r + 1])

        # print(dp)

        return dp[0][n-1]

image.png