Python solution with detailed explanation


  • 1
    G

    Solution

    Burst Balloons https://leetcode.com/problems/burst-balloons/

    Brute Force Backtracking Solution

    • The first naive solution is to use back-tracking. Then you can optimize back-tracking using caching. Back-tracking will have a complexity of O(N!). With cache optmization, some pruning will happen in the tree, but its complexity will still be a lot.
    class Solution(object):
        def get_key(self, nums):
            return "_".join(map(str, nums))
        
        def helper(self, nums, cache):
            if nums == []:
                return 0
            else:
                k = self.get_key(nums)
                if k in cache:
                    return cache[k]
                cache[k] = float('-inf')
                for i, x in enumerate(nums):
                    left, right = nums[i-1] if i > 0 else 1, nums[i+1] if i+1<len(nums) else 1
                    cache[k] = max(cache[k], self.helper(nums[0:i] + nums[i+1:], cache) + left*right*x)
                return cache[k]
        
        def maxCoins(self, nums):
            """
            :type nums: List[int]
            :rtype: int
            """
            return self.helper(nums, {})
    

    Optimized Solution using Divide and Conquer

    • Try thinking using divide and conquer. Pick an index, burst that balloon. Issue is that post bursting, the left and right halves around the burst balloon share a common boundary.
    • Instead, the insight is to define a sub-problem as finding the maximum coins possible within [low, high] of nums array.
    • Now let us pick an index i as the last burst balloon within that range.
    • The last burst balloon will be padded with nums[low-1] and nums[high+1]. So its contribution will be nums[low-1] * nums[high+1] * nums[i]
    • nums[i] is the last balloon to be burst which yield maximum coins when considering only ballons within nums[low] to nums[high]. Now when we reach nums[i] ready to be burst, what balloons is it padded with? It will be padded with nums[low-1] and nums[high+1]. Thus you need you take their contribution. This part is tricky - give it a careful though. If you understand the sub-problem formulation, then it is easy.
    • Now we can define a recursive formulation. Given that we pick index i as the last burst balloon to burst, the maximum coins which can be collected using balloons from low to high is:
      dp[low,high] = max(dp[low,high], nums[i] * nums[low-1] * nums[high + 1] + dp[low, i-1] + dp[i+1, high])
    • Simply use caching to solve this recurrence.
    • What is the complexity? Answer is: O(N^3). Why? There O(N^2) sub-problems (evident from the matrix to cache solutions). Each problem is O(N) complexity.
    from collections import defaultdict
    class Solution(object):
        def helper(self, nums, low, high, cache):
            if low > high:
                return 0
            elif low in cache and high in cache[low]:
                return cache[low][high]
            else:
                for i in range(low, high+1):
                    left_half, right_half = self.helper(nums, low, i-1, cache), self.helper(nums, i+1, high, cache)
                    left, right = nums[low-1] if low > 0 else 1, nums[high+1] if high+1<len(nums) else 1
                    cache[low][high] = max(cache[low][high], left_half + right_half + left*nums[i]*right)
                return cache[low][high]
        
        def maxCoins(self, nums):
            """
            :type nums: List[int]
            :rtype: int
            """
            cache = defaultdict(lambda: defaultdict(int))
            return self.helper(nums, 0, len(nums)-1, cache)
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.