Description
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
Solutions
1. DP
# Time: O(n^3)
# Space: O(n^2)
class Solution:
def maxCoins(self, nums: List[int]) -> int:
nums = [1] + [num for num in nums if num > 0] + [1]
n = len(nums)
dp = [[0 for _ in range(n)] for _ in range(n)]
for s in range(2, n):
for l in range(n - s):
r = l + s
for k in range(l + 1, r):
dp[l][r] = max(dp[l][r], nums[l] * nums[k] * nums[r] + dp[l][k] + dp[k][r])
return dp[0][n-1]
# 70/70 cases passed (432 ms)
# Your runtime beats 82.17 % of python3 submissions
# Your memory usage beats 100 % of python3 submissions (13.2 MB)