题目大意 给定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]