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.
Algorithm
Dynamic Programming (DP). Let dp[s][t] represent the maximum number of coins that can be obtained by bursting all the balloons between index s and t.
d p [ s ] [ t ] = m a x ( d p [ s ] [ k ] + d p [ k ] [ t ] + n u m s [ s ] ∗ n u m s [ k ] ∗ n u m s [ t ] ) dp[s][t] = max(dp[s][k] + dp[k][t] + nums[s] * nums[k] * nums[t]) dp[s][t]=max(dp[s][k]+dp[k][t]+nums[s]∗nums[k]∗nums[t])
For s < k < t s < k < t s<k<t.
Code
class Solution:def maxCoins(self, nums: List[int]) -> int:nums = [1] + nums + [1]nlen = len(nums)dp = [[0] * nlen for _ in range(nlen)]for l in range(2, nlen):for s in range(nlen - l):t = s + lfor k in range(s+1, t):if dp[s][t] < dp[s][k] + dp[k][t] + nums[s] * nums[k] * nums[t]:dp[s][t] = dp[s][k] + dp[k][t] + nums[s] * nums[k] * nums[t]return dp[0][nlen - 1]
