[leetcode 312]Burst Balloons原创解法

发表于 更新于

题目概述

312原题链接

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.

examples:
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

简单直接的解法

遍历回溯法，建立一个集合，把遍历过的数字放在该集合里。算法的复杂度是O(n!)。解法如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
class Solution1(object):
    def maxCoins(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        path = []
        max_path = [path]
        max = [0]
        s = [0]
        D = set()
        self.find(nums, path, D, s, max, max_path)
        print(max_path[0])
        return max[0]

    def find(self, nums, path, D, s, max, max_path):
        if len(path) == len(nums):
            if s[0] > max[0]:
                max[0] = s[0]
                max_path[0] = path[:]
        else:
            for i in range(len(nums)):
                if i not in D:
                    path.append(i)
                    D.add(i)
                    tmp = self.compute(i, nums, D)
                    s[0] += tmp
                    self.find(nums, path, D, s, max, max_path)
                    path.pop()
                    D.remove(i)
                    s[0] -= tmp

    def compute(self, i, nums, D):
        left, right = 1, 1
        for j in range(i - 1, -1, -1):
            if j not in D:
                left = nums[j]
                break
        for k in range(i + 1, len(nums)):
            if k not in D:
                right = nums[k]
                break
        return left * right * nums[i]

回顾矩阵链解法

以上的方法无疑会超时，但是它是我们理解问题，验证其它算法的基础。 我们希望能够得到一个多项式时间的解法，按照以往的经验，我们如果能够找到一个贪心算法是最好的， 但是如果我们能够有一个贪心算法，那么也一定能够有一个动态规划方法。CRLS对贪心和动态规划做了清楚的 描述，核心都是要找到最优子结构，并且证明存在最优子结构——这其实也是最难的部分，因为动态规划方法从来只是一个思想，本质上不过是 递归的一种优化而已。

CRLS中在动态规划一章中用了几个例子来详细展示动态规划方法。其中第二个例子就是矩阵链问题————如果有一个 矩阵链A1*A2*A3*A4，其中A1是1x5的矩阵，A2是5x1的矩阵，A3是1x5的矩阵，A4是5x1的矩阵。那么先计算A1*A2和A3*A4 则是比较好的，代价较小都是1x5x1=5。而A2*A3则是比较糟糕的，因为A2*A3的计算代价是5x1x5=25。

对给定的两个矩阵相乘A_ik*A_kj, 计算的代价是i*k*j。

等价转换

矩阵链中计算的代价是三个数相乘，而我们这里也是三个数字相乘。对于三个气球（数字）5·1·5，如果戳破第一个气球（数字），则得分（代价）是1x5x1，如果戳破第二个气球（数字） 得分（代价）是5x1x5，戳破第三个气球（数字）得分（代价）是1x5x1。对于1x5x1可以转换为1x5的矩阵和5x1的矩阵的代价。 5x1x5，可以转换为5x1的矩阵和1x5的矩阵的代价。最终，三个数字5·1·5可以等价转换为求解四个矩阵 A1*A2*A3*A4的最大计算代价的问题。所以第一步就是把n个数字转换为n+1个矩阵表示，第二步就是把矩阵链问题的递归求解中 的min改成max。如果这两个问题是等价的，那么我们的解法一定可以通过测试。并且似乎也不用去证明了。（其实这是最难的部分。）

以下是通过的memoization解法，算法的复杂度是O(n^2)，与矩阵链问题的复杂度一样：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution2(object):
    def maxCoins(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        n = len(nums)
        list = self.get(nums) # 转换为n+1个矩阵的表示。每个pair tuple对应矩阵的长和宽。
        print(list)
        n += 1
        m = [[None] * n for i in range(n)] # 声明一个子问题空间是n^2的记忆体
        print(m)
        for i in range(n):
            m[i][i] = 0

        return self.recursive(list, m, 0, n - 1)

    def get(self, nums):
        n = len(nums)
        list = [(1, nums[0])]
        for i in range(n):
            if (i + 1 < n):
                list.append((nums[i], nums[i + 1]))
            else:
                list.append((nums[i], 1))
        return list

    def recursive(self, list, m, i, j):
        if m[i][j] is not None:
            return m[i][j]
        else:
            max = -1
            for k in range(i, j):
                a = self.recursive(list, m, i, k)
                b = self.recursive(list, m, k + 1, j)
                v = a + b + list[i][0] * list[k][1] * list[j][1]
                if v > max :
                    max = v
            m[i][j] = max
            return m[i][j]