Burst Balloons

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