Skip to content
AI360Xpert
Back to 2-D Dynamic Programming
Hard

Burst Balloons

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.

Examples

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
Input:nums = [1,5]
Output:10
nums = [1,5] --> [5] --> [] coins = 1*1*5 + 1*5*1 = 10

Constraints

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

Dynamic Programming (Interval DP)

Approach

### Intuition If we think about bursting a balloon `i` first, the balloons to its left and right become adjacent, merging the subproblems. This makes it difficult to define independent subproblems. Instead, we can think in reverse: what is the LAST balloon to burst? If balloon `i` is the last one to burst, the subproblems on its left `[left, i-1]` and right `[i+1, right]` are completely independent! The coins gained for bursting `i` last in the interval `[left, right]` would be `nums[left-1] * nums[i] * nums[right+1]`. ### Logic We can add `1` to both ends of the `nums` array to handle the boundary conditions easily. Then we use a DP array `dp[left][right]` to represent the maximum coins we can collect by bursting all balloons in the interval `[left, right]`. For any interval `[left, right]`, we iterate through all possible last balloons `i` in this interval. The cost of bursting `i` last in this interval is: `dp[left][i-1] + (nums[left-1] * nums[i] * nums[right+1]) + dp[i+1][right]`. We take the maximum of this over all possible `i`. ### Step-by-step - Pad the `nums` array with `1` at the beginning and end. - Let `n` be the length of the new padded array. - Initialize a 2D DP array `dp` of size `n x n` with 0s. - Iterate the length of the interval `length` from 1 to `n - 2` (original balloons count). - Iterate the starting index `left` from 1 to `n - length - 1`. - The ending index `right` is `left + length - 1`. - Iterate `i` (the last balloon to burst) from `left` to `right`: - Calculate the coins collected: `dp[left][i-1] + nums[left-1] * nums[i] * nums[right+1] + dp[i+1][right]`. - Update `dp[left][right]` with the maximum coins collected. - Return `dp[1][n-2]`.

Complexity Analysis

Time Complexity
O(n^3)
Space Complexity
O(n^2)

Time complexity is O(n^3) because there are O(n^2) intervals and for each interval we do O(n) work to find the last balloon. Space complexity is O(n^2) for the DP table.

Solution.java
class Solution {    public int maxCoins(int[] nums) {        int n = nums.length;        int[] paddedNums = new int[n + 2];        paddedNums[0] = 1;        paddedNums[n + 1] = 1;        for (int i = 0; i < n; i++) {            paddedNums[i + 1] = nums[i];        }                int[][] dp = new int[n + 2][n + 2];                for (int len = 1; len <= n; len++) {            for (int left = 1; left <= n - len + 1; left++) {                int right = left + len - 1;                for (int i = left; i <= right; i++) {                    int coins = dp[left][i - 1] +                                 (paddedNums[left - 1] * paddedNums[i] * paddedNums[right + 1]) +                                 dp[i + 1][right];                    dp[left][right] = Math.max(dp[left][right], coins);                }            }        }                return dp[1][n];    }}