Burst Ballons

扎气球，这个题也是个标准的区间类DP，和stone game稍微不同的地方在于stone game每次合并完是变成一个大的个体继续存在，而这里扎完只代表这个气球不存在了，且它相邻两侧的气球就变成相邻的了，所以这里有两个比较需要注意到的点，第一就是当前区间[i,j]中无论选择任意i ≤ k ≤ j扎破都不影响这个区间外的决策，也就是说在[i, j]这个区间上最后扎的气球相邻的两个点必然是i - 1 和 j + 1，因此也可以看出状态方程如下

dp[i][j] = max(dp[i][j], nums[i - 1] * nums[i + 1] * nums[i] + dp[i][k - 1] + dp[k + 1][j], for all k in [i, j]

同时，还有一个关于边界的问题需要注意，即有可能扎破边界气球后左半边后者右半边已经没有气球了，这时应该算1，为了简化代码，不妨加入左右两排dummy row，这样坐标就从[0, n - 1]变成了[1, n]，需要注意一下，代码如下

class Solution(object):
    def maxCoins(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        n = len(nums)
        if not n:
            return 0

        ref = [([0] * (n + 2)) for _ in xrange(n + 2)]
        flag = [([False] * (n + 2)) for _ in xrange(n + 2)]

        return self.memoiz(nums, 1, n, ref, flag, n)

    def memoiz(self, nums, i, j, ref, flag, n):
        if flag[i][j]:
            return ref[i][j]

        flag[i][j] = True

        left = nums[i - 2] if i - 2 >= 0 else 1
        right = nums[j] if j < n else 1

        for index in xrange(i, j + 1):
            a = self.memoiz(nums, i, index - 1, ref, flag, n)
            b = self.memoiz(nums, index + 1, j, ref, flag, n)
            ref[i][j] = max(ref[i][j], left * right * nums[index - 1] + a + b)
        return ref[i][j]

这道题也可以看出，区间类DP的共性是求[0, n - 1]范围的一个最优解，但是具体到各个题目，判断求值的方式却不尽相同

还是for循环解法，此题的左右边界范围是个很麻烦的情况，需要两边加个1就好处理了

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

        for i in xrange(1, n + 1):
            for j in xrange(i, 0, -1):
                if i == j:
                    dp[j][i] = nums[j - 1] * nums[j] * nums[j + 1]
                else:
                    dp[j][i] = -sys.maxint
                    for k in xrange(j, i + 1):
                        dp[j][i] = max(dp[j][k - 1] + dp[k + 1][i] + nums[j - 1] * nums[k] * nums[i + 1], dp[j][i])

        return dp[1][n]

一种比较干净的写法，把单个元素的区间放到上一级去写

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

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

        return dp[1][n]