Burst Balloons

Problem: Burst Balloons

The key points is that we can get solution for n balloons from solution for n-1 balloons.

Code in Python:

class Solution(object):
    def maxCoins(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        nums = [1] + nums + [1]
        n = len(nums)
        dp = [[0] * n for _ in xrange(n)]

        for i in xrange(2, n):
            for l in xrange(0, n-i):
                r = l + i
                for j in xrange(l+1, r):
                    dp[l][r] = max(dp[l][r], nums[l]*nums[j]*nums[r]+dp[l][j]+dp[j][r])
        return dp[0][-1]

In this solution, we first try solutions when only burst 1 balloon, then we try solutions for 2 balloons. By repeating this, we can get solutions for n balloons.

For example, when we dealing with [3, 1, 5, 8], we first get 3, 15, 40, 40 by bursting each balloon. Then we look at sub-sequence [3, 1] and get 0 + 15 + 15 is a better solution than 3 + 5 + 0. Also when we look at [1, 5], we can see that 0 + 24 + 40 (burst 1 later) then 1) is a worse solution than 15 + 120 + 0 (burst 5 later). By repeating this, we can also get solutions for [3, 1, 5] since if we burst 3 at last in this group, we know solutions for [1, 5] and what we want to add is set 1,3,8. If we want to burst 1 at last, then the situation is split to [3] and [5] separately since they won't interfere each other and we need to calculate set 1,1,8.