Burst Balloons

偏执的太偏执、 2021-12-17 10:27 184阅读 0赞

Given `n` balloons, indexed from `0` to `n-1`. Each balloon is painted with a number on it represented by array `nums`. You are asked to burst all the balloons. If the you burst balloon `i` you will get `nums[left] * nums[i] * nums[right]` coins. Here `left` and `right` are adjacent indices of `i`. After the burst, the `left` and `right` then becomes adjacent.

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

**Note:**  
(1) You may imagine `nums[-1] = nums[n] = 1`. They are not real therefore you can not burst them.  
(2) 0 ≤ `n` ≤ 500, 0 ≤ `nums[i]` ≤ 100

**Example:**

Given `[3, 1, 5, 8]`

Return `167`

nums = [3,1,5,8] --> [3,5,8] -->   [3,8]   -->  [8]  --> []
       coins =  3*1*5      +  3*5*8    +  1*3*8      + 1*8*1   = 167

这题如果考虑按题目的意思从第一个爆裂的气球挑选起，接着是第二个，第三个，这个过程比较困难．毕竟如果爆掉一个气球，其两边的气球也就相邻了．但是如果我们考虑反过来的思路，我们先挑选最后一个爆掉的气球．此时所有气球都已经爆掉，则其左右的气球就是假想的nums\[-1\]和nums\[n\].此时爆裂所附加的coins值可以确定，再倒过来考虑倒数第二个气球，则也是这样的情况．其周围还没有爆裂的气球已知．所以这题采取top down的思路要比bottom up的思路简单．但是每次top down挑选爆裂的气球的时候也需要枚举一边气球，这往下有会有枚举，自问题重复很多，采用top-down with memoization的DP方法.因为要枚举爆裂的气球,我们先得定义需要爆裂的气球在什么区间之间.所以这是一个区间型DP.

１．我们定义DP\[i\]\[j\]为把第i个至第j个气球打爆的最大价值.

２．然后是定义转换状态.DP\[i\]\[j\] = max\{DP\[i\]\[k-1\]+DP\[k+1\]\[j\]+nums\[i-1\]\*nums\[k\]\*nums\[j+1\]\}.注意其中最后一项打爆一个气球其相邻值的反应.我们的解法是自顶向下的.所以在求解DP\[i\]\[j\]枚举切分位的时候，DP\[i\]\[k-1\]和DP\[k+1\]\[j\]中的气球已经全部爆掉，此时应该考虑的是nums\[i-1\]和nums\[j+1\].注意此时要考虑i-1和j+1越界的情况．

３．初始化状态DP\[i\]\[j\] (i<j)等于０，DP\[i\]\[i\] = nums\[i\]\*nums\[i-1\]\*nums\[i+1\] **注意这里并不是０**．毕竟求解到DP\[i\]\[i\]时其左右的气球还没爆呢．区间从大往下，不断夹逼．

４．返回值DP\[0\]\[n-1\]

代码如下：

class Solution(object):
        def maxCoins(self, nums):
            """
            :type nums: List[int]
            :rtype: int
            """
            #top down solution. alll the ballons that equal to 0 can be eliminated firstly.
            n = len(nums)
            dp = [[-1]*n for i in xrange(n)]
            return self.memory_search(nums, dp, 0, n-1)
            
        def memory_search(self, nums, dp, start, end):
            if start > end:
                return 0
            if dp[start][end] >= 0:
                return dp[start][end]
            value = 1
            if start >= 1:
                value *= nums[start-1] 
            else:
                value = 1
            if end < len(nums)-1:
                value *=  nums[end + 1]
            #if start == end:
            #    value *= nums[start]
            #    dp[start][end] = value
            #    return dp[start][end]
            
            dp[start][end] = -sys.maxint - 1
            for k in xrange(start, end+1):
                left = self.memory_search(nums, dp, start, k-1)
                right = self.memory_search(nums, dp, k+1, end)
                dp[start][end] = max(left + right + value *nums[k], dp[start][end])
            return dp[start][end]

这种不过做法要处理边界比较麻烦,可以开辟一个新数组，在其左右填充各填充一个１．另外题意给出的气球价值可能为０，但是０值的气球本身不产生价值，对最后的结果没有影响．所以开始时就去掉比较好．

这种简化过的代码如下：

class Solution(object):
        def maxCoins(self, nums):
            """
            :type nums: List[int]
            :rtype: int
            """
            #top down solution. alll the ballons that equal to 0 can be eliminated firstly.
            arr = [1]
            for i in nums:
                if i:
                    arr.append(i)
            arr.append(1)
            print arr
            n = len(arr)
            dp = [[-1]*n for i in xrange(n)]
            return self.memory_search(arr, dp, 1, n-2)
            
        def memory_search(self, arr, dp, start, end):
            if start > end:
                return 0
            if dp[start][end] >= 0:
                return dp[start][end]
            dp[start][end] = -sys.maxint - 1
            for k in xrange(start, end+1):
                left = self.memory_search(arr, dp, start, k-1)
                right = self.memory_search(arr, dp, k+1, end)
                dp[start][end] = max(left + right + arr[k]*arr[start-1]*arr[end+1], dp[start][end])
            return dp[start][end]

另外这题也可以用区间长度自底向上来做，详见[leetcode discuss][]

转载于:https://www.cnblogs.com/sherylwang/p/5616021.html

[leetcode discuss]: https://leetcode.com/discuss/72216/share-some-analysis-and-explanations