LC312 - Burst Balloons

Problem

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

Input: nums = [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

Solution

DFS

The naive solution would be a DFS of a decision tree, which would have $O(n^n)$ time complexity due to the width and depth of the tree.

Cached DFS

Time complexity of this approach is about $O(n^2)$. Update with explanation will come later.

def maxCoins(self, nums: List[int]) -> int:
	nums = [1] + nums + [1]
	@cache
	def dfs(l, r):
		if l > r:
			return 0
		tmp = 0
		for i in range(l, r + 1):
			coins = nums[l - 1] * nums[i] * nums[r+1]
			coins += dfs(l, i-1) + dfs(i+1, r)
			tmp = max(tmp, coins)
		return tmp
	return dfs(1, len(nums)-2)