Question

Formatted question description: https://leetcode.ca/all/312.html

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 i^th 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

Algorithm

Maintain a two-dimensional dynamic array dp, where dp[i][j] represents the most gold coins that can be obtained by bursting all balloons in the interval [i,j].

dp[i][j] = max(dp[i][j], nums[i-1] * nums[k] * nums[j + 1] + dp[i][k-1] + dp[ k + 1][j]) (i ≤ k ≤ j )

Example [3, 1, 5, 8], the general traversal order is:

[3] -> [3, 1] -> [3, 1, 5] -> [3, 1, 5, 8] -> [1] -> [1, 5] -> [1, 5, 8 ] -> [5] -> [5, 8] -> [8]

Obviously it is not the traversal order we need. The correct order should be to first traverse all the intervals of length 1, then the intervals of length 2, and then accumulate the lengths in turn, until the entire interval is traversed:

[3] -> [1] -> [5] -> [8] -> [3, 1] -> [1, 5] -> [5, 8] -> [3, 1, 5] -> [1, 5, 8] -> [3, 1, 5, 8]

In fact, only the upper right triangle area of the dp array is updated here, and the final value to be returned is stored in dp[1][n], where n is the number of array nums before adding 1 at both ends.

Code

public class Burst_Balloons {


    class Solution {
        public int maxCoins(int[] nums) {

            int n = nums.length;

            // padding start/end with 1
            int[] newNums = new int[n + 2];
            for (int i = 0; i < nums.length; i++) {
                newNums[i + 1] = nums[i];
            }
            newNums[0] = 1;
            newNums[n + 1] = 1;

            int[][] dp = new int[nums.length + 2][nums.length + 2];

            nums = newNums;
            for (int len = 1; len <= n; ++len) {
                for (int i = 1; i <= n - len + 1; ++i) {
                    int j = i + len - 1;
                    for (int k = i; k <= j; ++k) {
                        dp[i][j] = Math.max(dp[i][j], nums[i - 1] * nums[k] * nums[j + 1] + dp[i][k - 1] + dp[k + 1][j]);
                    }
                }
            }

            return dp[1][n];
        }
    }

    // brute force, basically try every possible combination, just with some cache intermediate results
    class Solution_bruteForce {
        public int maxCoins(int[] nums) {

            // max coins from index-i to index-j
            int[][] dp = new int[nums.length][nums.length];
            return maxCoins(nums, dp, 0, nums.length - 1);
        }

        private int maxCoins(int[] nums, int[][] dp, int start, int end) {
            if (start > end) {
                return 0;
            }

            if (dp[start][end] != 0) {
                return dp[start][end];
            }

            int max = nums[start];
            for (int i = start; i <= end; i++) {
                int val = maxCoins(nums, dp, start, i - 1) +
                            // @note: not i-1, should be start-1
                            getNumsValue(nums, start - 1) * getNumsValue(nums, i) * getNumsValue(nums, end + 1) +
                            maxCoins(nums, dp, i + 1, end);

                max = Math.max(max, val);
            }
            dp[start][end] = max;

            return dp[start][end];
        }

        private int getNumsValue(int[] nums, int i) {

            return i == -1 || i == nums.length ? 1: nums[i];
        }
    }
}

############

class Solution {
    public int maxCoins(int[] nums) {
        int[] vals = new int[nums.length + 2];
        vals[0] = 1;
        vals[vals.length - 1] = 1;
        System.arraycopy(nums, 0, vals, 1, nums.length);
        int n = vals.length;
        int[][] dp = new int[n][n];
        for (int l = 2; l < n; ++l) {
            for (int i = 0; i + l < n; ++i) {
                int j = i + l;
                for (int k = i + 1; k < j; ++k) {
                    dp[i][j]
                        = Math.max(dp[i][j], dp[i][k] + dp[k][j] + vals[i] * vals[k] * vals[j]);
                }
            }
        }
        return dp[0][n - 1];
    }
}

// OJ: https://leetcode.com/problems/burst-balloons/
// Time: O(N^3)
// Space: O(N^2)
class Solution {
public:
    int maxCoins(vector<int>& A) {
        if (A.empty()) return 0;
        int N = A.size();
        vector<vector<int>> dp(N, vector<int>(N));
        for (int i = 0; i < N; ++i) dp[i][i] = (i - 1 < 0 ? 1 : A[i - 1]) * A[i] * (i + 1 >= N ? 1 : A[i + 1]);
        for (int i = N - 2; i >= 0; --i) {
            for (int j = i + 1; j < N; ++j) {
                for (int k = i; k <= j; ++k) {
                    dp[i][j] = max(dp[i][j],
                                   (k - 1 < i ? 0 : dp[i][k - 1])
                                   + (i - 1 < 0 ? 1 : A[i - 1]) * A[k] * (j + 1 >= N ? 1 : A[j + 1])
                                   + (k + 1 > j ? 0 : dp[k + 1][j]));
                }
            }
        }
        return dp[0][N - 1];
    }
};

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

############

class Solution(object):
  def maxCoins(self, nums):
    """
    :type nums: List[int]
    :rtype: int
    """
    if len(nums) == 0:
      return 0
    nums = [1] + nums + [1]
    dp = [[-1] * (len(nums) + 2) for _ in range(0, len(nums) + 2)]

    def dc(start, end, dp, nums):
      if dp[start][end] != -1:
        return dp[start][end]
      if start > end:
        return 0
      for i in range(start, end + 1):
        left = dc(start, i - 1, dp, nums)
        right = dc(i + 1, end, dp, nums)
        dp[start][end] = max(dp[start][end], left + right + nums[start - 1] * nums[i] * nums[end + 1])
      return dp[start][end]

    dc(1, len(nums) - 2, dp, nums)
    return dp[1][len(nums) - 2]

func maxCoins(nums []int) int {
	vals := make([]int, len(nums)+2)
	for i := 0; i < len(nums); i++ {
		vals[i+1] = nums[i]
	}
	n := len(vals)
	vals[0], vals[n-1] = 1, 1
	dp := make([][]int, n)
	for i := 0; i < n; i++ {
		dp[i] = make([]int, n)
	}
	for l := 2; l < n; l++ {
		for i := 0; i+l < n; i++ {
			j := i + l
			for k := i + 1; k < j; k++ {
				dp[i][j] = max(dp[i][j], dp[i][k]+dp[k][j]+vals[i]*vals[k]*vals[j])
			}
		}
	}
	return dp[0][n-1]
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

function maxCoins(nums: number[]): number {
    let n = nums.length;
    let dp = Array.from({ length: n + 1 }, v => new Array(n + 2).fill(0));
    nums.unshift(1);
    nums.push(1);
    for (let i = n - 1; i >= 0; --i) {
        for (let j = i + 2; j < n + 2; ++j) {
            for (let k = i + 1; k < j; ++k) {
                dp[i][j] = Math.max(
                    nums[i] * nums[k] * nums[j] + dp[i][k] + dp[k][j],
                    dp[i][j],
                );
            }
        }
    }
    return dp[0][n + 1];
}

312 - Burst Balloons

Question

Algorithm

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

Code

All Problems

All Solutions