My TLE Python O(N^3) DP Solution with comments

• class Solution(object):

``````def maxCoins(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
n = len(nums)
nums.insert(0, 1)
nums.append(1)
# table[i][j] stores the optimal result of bursting balloon starts at i and the length is j
# balloon starts from 1 to n
table = [[0 for i in xrange(n-I+1)] for I in xrange(n+1)]
table.insert(0, [])

for i in xrange(1, n+1):
table[i][1] = nums[i-1] * nums[i] * nums[i+1]

for l in xrange(2, n+1): # length from 2 to n
for j in xrange(1, n-l+2): # balloon can starts from balloon 1 to balloon n-l+1
maximum = 0
for i in xrange(j, j+l): # balloon i is the last burst balloon
if i < j+l-1:
temp = table[j][i-j] + table[i+1][j+l-i-1] + nums[i]*nums[j-1]*nums[j+l]
else:
temp = table[j][i-j] + nums[i]*nums[j-1]*nums[j+l]
maximum = max(maximum, temp)
table[j][l] = maximum
return table[1][n]``````

• I think they changed the test cases so this solution can pass now.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.