312. Burst Balloons¶

LeetCode Problem View on GitHub

312. Burst Balloons

Hard

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.

Example 1:

Input: nums = [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

Example 2:

Input: nums = [1,5]
Output: 10

Constraints:

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

Solution¶

class Solution {
    private int dp[][];
    public int maxCoins(int[] nums) {
        int n = nums.length;
        dp = new int[n + 1][n + 1];
        for (int current[] : dp)
            Arrays.fill(current, -1);
        int arr[] = new int[n + 2];
        arr[0] = 1;
        arr[n + 1] = 1;
        for (int i = 1; i <= n; i++)
            arr[i] = nums[i - 1];
        int res = solve(1, n, arr);
        return res;    
    }
    private int solve(int i, int j, int arr[]) {
        if (i > j) return 0;
        if (dp[i][j] != -1)
            return dp[i][j];
        int ans = Integer.MIN_VALUE;
        for (int k = i; k <= j; k++) {
            ans = Math.max(ans, arr[i - 1] * arr[k] * arr[j + 1] + solve(i, k - 1, arr) + solve(k + 1, j, arr));
        }
        return dp[i][j] = ans;
    }
}

Complexity Analysis¶

• Time Complexity: O(?)
• Space Complexity: O(?)

Approach¶

Detailed explanation of the approach will be added here