This is a Leetcode problem -
Given
n
balloons, indexed from0
ton-1
. Each balloon is painted with a number on it represented by arraynums
. You are asked to burst all the balloons. If you burst the ballooni
you will getnums[left] * nums[i] * nums[right]
coins. Hereleft
andright
are adjacent indices ofi
. After the burst, theleft
andright
then become 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
Here is my solution to this challenge -
# Uses dynamic programming
def max_coins(nums):
"""
:type nums: List[int]
:rtype: int
"""
nums = [1] + nums + [1]
n = len(nums)
dp = [[0] * n for i in range(n)]
for j in range(2, n):
for i in range(j - 2, -1, -1):
for k in range(i + 1,j):
dp[i][j] = max(dp[i][j], dp[i][k] + dp[k][j] + nums[i] * nums[j] * nums[k])
return dp[0][-1]
Here is the Leetcode result (70 test cases) -
So, I would like to know whether I could make this program shorter and more efficient.
dp = [[0] * n for i in range(n)]
can bedp = [[0] * n for _ in range(n)]
. By convention in python if we dont use the index variable we just use_
\$\endgroup\$ – user172231 Jun 5 '19 at 14:34