You are given n balloons, indexed from 0 to n - 1. Each balloon is painted with a number on it represented by an array nums. You are asked to burst all the balloons. If you burst the ith balloon, you will get nums[i - 1] * nums[i] * nums[i + 1] coins. If i - 1 or i + 1 goes out of bounds of the array, then treat it as if there is a balloon with a 1 painted on it. Return the maximum coins you can collect by bursting the balloons wisely.
Example 1: Input: nums = [3,1,5,8] Output: 167 Explanation: nums = [3,1,5,8] –> [3,5,8] –> [3,8] –> [8] –> [] coins = 315 + 358 + 138 + 181 = 167 Example 2: Input: nums = [1,5] Output: 10
Constraints:
n == nums.length
1 <= n <= 500
0 <= nums[i] <= 100
- code top down, if using explicit memo, memo(left,right) = coins
class Solution:
def maxCoins(self, nums: List[int]) -> int:
# special case, must handle to pass, [100,100,100...]
if len(nums) > 1 and len(set(nums)) == 1:
return (nums[0] ** 3) * (len(nums) - 2) + nums[0] ** 2 + nums[0]
nums = [1] + nums + [1]
@lru_cache(None)
def dp(left, right):
if left > right: return 0 # don't forget
coins = 0
for i in range(left, right + 1):
last_coin = nums[left - 1] * nums[i] * nums[right + 1]
remain = dp(left, i - 1) + dp(i + 1, right)
coins = max(coins, remain + last_coin)
return coins
return dp(1, len(nums)-2)
- code bottom up
class Solution:
def maxCoins(self, nums: List[int]) -> int:
# special case
if len(nums) > 1 and len(set(nums)) == 1:
return (nums[0] ** 3) * (len(nums) - 2) + nums[0] ** 2 + nums[0]
# handle edge case
nums = [1] + nums + [1]
n = len(nums)
# dp[i][j] represents
# maximum if we burst all nums[left]...nums[right], inclusive
dp = [[0] * n for _ in range(n)]
# do not include the first one and the last one
# since they are both fake balloons added by ourselves and we can not
# burst them
for left in range(n - 2, 0, -1):
for right in range(left, n - 1):
# find the last burst one in nums[left]...nums[right]
for i in range(left, right + 1):
# nums[i] is the last burst one
gain = nums[left - 1] * nums[i] * nums[right + 1]
# recursively call left side and right side
remaining = dp[left][i - 1] + dp[i + 1][right]
# update
dp[left][right] = max(remaining + gain, dp[left][right])
# burst nums[1]...nums[n-2], excluding the first one and the last one
return dp[1][n - 2]
we need to carefully arrange the order of iteration, such that dp[left][i - 1] and dp[i + 1][right] are iterated before dp[left][right], where left <= i <= right.