pydata

Keep Looking, Don't Settle

leetcode 312. Burst Balloons

312. Burst Balloons

题目大意 给定n个气球,每个气球有一个数字,用数组nums来表示n个气球上面的数字。如果气球i被打破,那么你会得到nums[left] * nums[i] * nums[right] 。 这里left和right分别为气球i的左右两边的气球。打破所有的气球后把所有的数字相加,求解怎么打破这些气球使得最后得到的数字最大。

比如给定 [3, 1, 5, 8],最大可以得到 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[i]到nums[j],加入中间有一个k,对应的nums[k],如果nums[k]没有被打破,那么nums[k]把nums[i]到nums[j]分成两个子串,分别为nums[i]到nums[k-1]和nums[k+1]到nums[j]。这样我们可以对这两个子串分别求解打破以后的最大值,然后对不同的k来寻找最后的最大值,这样把一个nums[i]到nums[j]的大的问题就拆分成两个小的问题来求解。

1. 记忆化递归

class Solution(object):
    def maxCoins(self, nums):
        nums.insert(0, 1)
        nums.append(1)
        n = len(nums)
        dp = [[0 for _ in range(n + 1)] for _ in range(n + 1)]
        def divid(nums, dp, low, high):
            if low + 1 == high:
                return 0
            if dp[low][high] > 0:
                return dp[low][high]
            ans = 0
            for i in range(low + 1, high):
                ans = max(ans, nums[low]*nums[i]*nums[high] + divid(nums, dp, low, i) + divid(nums, dp, i, high))
            dp[low][high] = ans
            return ans
        return divid(nums, dp, 0, n - 1)

2. 递推/态规划

class Solution(object):
    def maxCoins(self, nums):
        n = len(nums)
        if n == 0:
            return 0
        nums.insert(0, 1)
        nums.append(1)
        c = [[0 for _ in range(n+2)] for _ in range(n+2)]
        for l in range(1, n + 1):
            # l is the len between j(include j) and i, so l = j - i + 1
            for i in range(1, n - l + 2):
                j = i + l - 1
                for k in range(i, j + 1):
                    c[i][j] = max(c[i][j], c[i][k-1] + nums[i-1]*nums[k]*nums[j+1] + c[k+1][j])
        return c[1][n]
class Solution(object):
    def maxCoins(self, nums):
        n = len(nums)
        if n == 0:
            return 0
        nums.insert(0, 1)
        nums.append(1)
        c = [[0 for _ in range(n+2)] for _ in range(n+2)]
        for i in range(n-1, -1, -1):
            for j in range(i + 2, n + 2):
                for k in range(i + 1, j):
                    c[i][j] = max(c[i][j], c[i][k] + nums[i]*nums[k]*nums[j] + c[k][j])
        return c[0][n+1]