#312

Hard

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Burst Balloons

Burst Balloons is a hard dynamic programming problem requiring careful state transitions to maximize coins collected efficiently.

array dynamic programming

Problem Statement

You are given an array nums representing n balloons, each painted with a number. Your task is to burst all balloons one by one to maximize coins collected.

Bursting the ith balloon yields coins equal to nums[i - 1] * nums[i] * nums[i + 1], treating out-of-bound neighbors as 1. Return the maximum coins achievable by choosing the bursting order optimally.

Examples

Example 1

Input: nums = [3,1,5,8]

Output: 167

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

Example 2

Input: nums = [1,5]

Output: 10

Example details omitted.

Constraints

n == nums.length
1 <= n <= 300
0 <= nums[i] <= 100

Solution Approach

Augment the array and define DP state

Insert 1 at the start and end of nums to simplify edge cases. Define dp[i][j] as the maximum coins obtainable by bursting all balloons between index i and j exclusively.

Recursive state transition

For each subarray (i,j), consider each balloon k as the last to burst. Update dp[i][j] = max(dp[i][j], dp[i][k] + nums[i]*nums[k]*nums[j] + dp[k][j]) to capture maximum coins from combining left, right, and last burst.

Iterative DP and memoization

Fill dp table iteratively by increasing subarray lengths or use memoized recursion. This ensures overlapping subproblems are solved once and total time remains manageable for n up to 300.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n^3) due to iterating all subarrays and possible last balloons within each. Space complexity is O(n^2) for the DP table storing maximum coins for all ranges.

What Interviewers Usually Probe

Expect discussion of recursive state definition versus iterative DP filling.
Look for correct handling of boundary conditions using virtual balloons of value 1.
Check awareness of overlapping subproblems and use of memoization or DP table.

Common Pitfalls or Variants

Common pitfalls

Forgetting to pad nums with 1 at both ends leading to index errors.
Incorrectly defining DP state, such as including endpoints instead of exclusive ranges.
Neglecting to iterate all possible last-burst positions within a subarray.

Follow-up variants

Maximizing coins when balloons can have negative numbers, requiring careful multiplication handling.
Bursting balloons with additional constraints, e.g., only adjacent balloons can be burst next.
Adapting the DP approach to count number of distinct maximum-coin sequences.

FAQ

What is the key dynamic programming pattern in Burst Balloons?

The problem uses state transition DP where each balloon is considered as the last to burst in a subarray, allowing optimal coin calculation.

How do I handle edge balloons when calculating coins?

Treat out-of-bound neighbors as 1 by padding the array at both ends, simplifying calculations for first and last balloons.

Is recursion sufficient or should I use iterative DP?

Memoized recursion works, but iterative DP ensures all subarrays are processed systematically and avoids stack overflows for large n.

Why is time complexity O(n^3) for Burst Balloons?

Each of the O(n^2) subarrays requires iterating O(n) possible last-burst positions, giving total O(n^3) operations.

Can this DP approach handle arrays up to length 300 efficiently?

Yes, with proper memoization or DP table filling, O(n^3) operations are feasible for n up to 300 without exceeding time limits.

terminal

Solution

Solution 1: Dynamic Programming

Let's denote the length of the array `nums` as $n$. According to the problem description, we can add a $1$ to both ends of the array `nums`, denoted as `arr`.

1

2

3

4

5

6

7

8

9

10

class Solution:
    def maxCoins(self, nums: List[int]) -> int:
        n = len(nums)
        arr = [1] + nums + [1]
        f = [[0] * (n + 2) for _ in range(n + 2)]
        for i in range(n - 1, -1, -1):
            for j in range(i + 2, n + 2):
                for k in range(i + 1, j):
                    f[i][j] = max(f[i][j], f[i][k] + f[k][j] + arr[i] * arr[k] * arr[j])
        return f[0][-1]

Continue Practicing

#313 super ugly number #309 best time to buy and sell stock with cooldown #322 coin change