312. 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:

• You may imagine nums[-1] = nums[n] = 1. They are not real therefore you can not burst them.
• 0 ≤ n ≤ 500, 0 ≤ nums[i] ≤ 100

Example:

``````Input: [3,1,5,8]
Output: 167
Explanation: 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
``````

# 解题方法

``````c[i][j] = max(c[i][j], self.dfs(nums, c, i, k - 1) + nums[i - 1] * nums[k] * nums[j + 1] + self.dfs(nums, c, k + 1, j))
``````

``````class Solution(object):
def maxCoins(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
n = len(nums)
nums.insert(0, 1)
nums.append(1)
c = [[0] * (n + 2) for _ in range(n + 2)]
return self.dfs(nums, c, 1, n)

def dfs(self, nums, c, i, j):
if i > j: return 0
if c[i][j] > 0: return c[i][j]
if i == j: return nums[i - 1] * nums[i] * nums[i + 1]
res = 0
for k in range(i, j + 1):
res = max(res, self.dfs(nums, c, i, k - 1) + nums[i - 1] * nums[k] * nums[j + 1] + self.dfs(nums, c, k + 1, j))
c[i][j] = res
return c[i][j]
``````

DP一般都可以通过记忆化搜索来改出来，但是我不会。。很遗憾，参考了别人的代码，还是没搞懂。。

``````class Solution(object):
def maxCoins(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
n = len(nums)
nums.insert(0, 1)
nums.append(1)
dp = [[0] * (n + 2) for _ in range(n + 2)]
for len_ in range(1, n + 1):
for left in range(1, n - len_ + 2):
right = left + len_ - 1
for k in range(left, right + 1):
dp[left][right] = max(dp[left][right], dp[left][k - 1] + nums[left - 1] * nums[k] * nums[right + 1] + dp[k + 1][right])
return dp[1][n]
``````