312.Burst_Balloons(Hard).md

312. Burst Balloons (Hard)

Date and Time: Oct 31, 2024, 23:42 (EST)

Link: https://leetcode.com/problems/burst-balloons/

Question:

You are given n balloons, indexed from 0 to n - 1. Each balloon is painted with a number on it represented by an array nums. You are asked to burst all the balloons.

If you burst the ith balloon, you will get nums[i - 1] * nums[i] * nums[i + 1] coins. If i - 1 or i + 1 goes out of bounds of the array, then treat it as if there is a balloon with a 1 painted on it.

Return the maximum coins you can collect by bursting the balloons wisely.

Example 1:

Input: nums = [3,1,5,8]

Output: 167

Explanation:
nums = [3,1,5,8] --> [3,5,8] --> [3,8] --> [8] --> []
coins = 315 + 358 + 138 + 181 = 167

Example 2:

Input: nums = [1,5]

Output: 10

Constraints:

• n == nums.length

• 1 <= n <= 300

• 0 <= nums[i] <= 100

Walk-through:

Build 2D dp table to save how many coins we need for a range [l, r]. We loop over each balloon, and we assume the current balloon will be the last to burst, we take how many coins we need to burst this balloon in the end add it with how many coins we need for its left subarray and right subarray.

Python Solution:

class Solution:
    def maxCoins(self, nums: List[int]) -> int:
        # Run recursion on each element
        # Each i is the # of coins we can get if we burst this ith ballon in the end, so we need to calculate all max coins its left, right subarrays can get

        # 1, [1, 5], 1
        # For [1]: coins = 1 * 1 * 1 + dfs(i+1, r)
        # dp[(l, r)] = max(dp[(l, r)], coins)
        # For [5]: 1 * 5 * 1 + dfs(l, i-1)

        # TC: O(n^3), SC: O(n^2)
        dp = {}     # {(l, r): max_coins}
        nums = [1] + nums + [1]
        def backtrack(l, r):
            if l > r:
                return 0
            if (l, r) in dp:
                return dp[(l, r)]
                
            max_coins = 0
            for i in range(l, r+1):
                coins = nums[l-1] * nums[i] * nums[r+1]
                coins += backtrack(l, i-1) + backtrack(i+1, r)
                max_coins = max(coins, max_coins)
            
            dp[(l, r)] = max_coins
            return max_coins
        
        return backtrack(1, len(nums)-2)

Time Complexity: $O(n^3)$, we loop over n balloon, and for every balloon, we need to check the dp table, which takes $O(n^2)$.
Space Complexity: $O(n^2)$, n balloon can form pairs with other n-1 balloons.