HardDynamic Programming
Burst Balloons
Maximum coins from bursting balloons
Solution Approach
DP on intervals. Think backwards: last balloon to burst in range. Combine subproblems.
Implementation
def maxCoins(nums):
n = len(nums)
balloons = [1] + nums + [1]
dp = [[0] * (n + 2) for _ in range(n + 2)]
for length in range(3, n + 3):
for left in range(n + 2 - length):
right = left + length - 1
for mid in range(left + 1, right):
dp[left][right] = max(dp[left][right],
balloons[left] * balloons[mid] * balloons[right] +
dp[left][mid] + dp[mid][right])
return dp[0][n + 1]Complexity Analysis
Time Complexity
O(n³)Space Complexity
O(n²)Complexity
Time:O(n³)
Space:O(n²)
Asked at
GoogleAmazon