n balloons, indexed from
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
right are adjacent indices of
i. After the burst, the
right then becomes adjacent.
Find the maximum coins you can collect by bursting the balloons wisely.
- You may imagine
nums[-1] = nums[n] = 1. They are not real therefore you can not burst them.
- 0 ≤
n≤ 500, 0 ≤
Input: [3,1,5,8] Output: 167 Explanation: nums = [3,1,5,8] --> [3,5,8] --> [3,8] -->  -->  coins = 3*1*5 + 3*5*8 + 1*3*8 + 1*8*1 = 167
# Time: O(n^3) # Space: O(n^2) class Solution: def maxCoins(self, nums: List[int]) -> int: nums =  + [num for num in nums if num > 0] +  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[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)