Question

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

 312	Burst Balloons

 Given n balloons, indexed from 0 to n-1.
 Each balloon is painted with a number on it represented by array nums.

 You are asked to burst all the balloons.
 If the you burst balloon i you will get nums[left] * nums[i] * nums[right] coins.
 Here left and right are adjacent indices of i. After the burst, the left and right then becomes adjacent.

 Find the maximum coins you can collect by bursting the balloons wisely.

 Note:

 You may imagine nums[-1] = nums[n] = 1. They are not real therefore you can not burst them.
 0 ≤ n ≤ 500, 0 ≤ nums[i] ≤ 100

 Example:

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

 @tag-dp

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

Java

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];
        }
    }
}

All Problems

All Solutions