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

Analysis

A very nice analysis on LeetCode talking about several approaches from brute-force to divide and conquer as well as dynamic programming:

https://leetcode.com/problems/burst-balloons/discuss/76228/Share-some-analysis-and-explanations

一、利用分治法Divide and Conquer结合记忆化memoization

二、或者利用区间型动态规划Dynamic Programming

Divide and Conquer with Memoization

https://mnmunknown.gitbooks.io/algorithm-notes/625,_dong_tai_gui_hua_ff0c_qu_jian_lei_dp.html

https://leetcode.com/problems/burst-balloons/discuss/76245/Easiest-Java-Solution

subproblems are overlapped, so we can use divide and conquer + cache

• Balloons 0, 1, ..., n - 1

• What is the max value if we burst all of them[0, n - 1]?

• Let's first consider bursting[start, end] (including start and end boundaries)

• Imagine index i as the last one in the interval to be bursted

• [start, ... i - 1, (i), i + 1 ... end]

• Before the end, we already bursted [start, i - 1] and [i + 1, end]

• Before the end, boundaries start - 1 , i , end + 1 are always there

• This helps us calculate coins without worrying about details inside[start, i - 1] and [i + 1, end]

• So the range can be divided into start - 1 ,maxCoin(start, i - 1), i, maxCoins(i + 1, end), end + 1

基本思想就是在区间[start, end]中循环i，i作为该区间内最后被爆的气球，这样区间被分成了左右两个区间，再依次递归地寻找 [start, i - 1] 和 [i + 1, end] 的区间。这样就变成了子问题，而子问题区间上是可能有重叠的，因此可以用memoization来优化递归。

Dynamic Programming

这题的难点在于，如何在动态变化的数组中，正确定义并计算subproblem.

因为数组一直在变化，如何计算每次打爆获得的coin呢？

是否可以将子问题定义为寻找(left, right)区间内能得到最多的coin数目？ 难想到的是从最后被打爆的气球入手，这种情况下，区间的左右两个两个元素就是确定的，而改变（循环i）区间内最后被打爆的气球则会得到不同的结果，从而找到最大

State:

• dp[i][j]表示 i 到 j 区间中，打爆所有气球的最大coin数目

Function:

• 对于所有k属于{i,j}, 表示第k号气球最后打爆。k is the last balloon to burst.

  • midValue = arr[i- 1] * arr[k] * arr[j + 1];

  • dp[i][j] = max(dp[i][k-1] + d[k+1][j] + midvalue)

Initialize:

• for each i

  • dp[i][i] = 0

Answer:

• dp[0][n-1]

Solution

Divide & Conquer + Recursive + Memoization - Easy to Understand Solution (16 ms, faster than 14.04%)

https://leetcode.com/problems/burst-balloons/discuss/76245/Easiest-Java-Solution

start, end boundary included (boundaries will be burst)

[start, ... i - 1, (i), i + 1 ... end]

class Solution {
    public int maxCoins(int[] nums) {
        int[][] dp = new int[nums.length][nums.length];
        return maxCoinsHelper(nums, 0, nums.length - 1, dp);
    }
    public int maxCoinsHelper(int[] nums, int start, int end, int[][] dp) {
        if (start > end) return 0;
        if (dp[start][end] != 0) return dp[start][end];
        int max = 0;
        for (int i = start; i <= end; i++) {
            int val = maxCoinsHelper(nums, start, i - 1, dp) + 
                maxCoinsHelper(nums, i + 1, end, dp) + 
                getVal(nums, start - 1) * getVal(nums, i) * getVal(nums, end + 1);
            max = Math.max(max, val);
        }
        dp[start][end] = max;
        return max;
    }
    private int getVal(int[] nums, int i) {
        if (i == -1 || i == nums.length) {
            return 1;
        }
        return nums[i];
    }
}

*(Favorite) - Same idea as above (Divide & Conquer with Memoization) but faster performance (6ms 87.86%)

Building a new array first for faster access, compared to above getVal() function

public class Solution {
    public int maxCoins(int[] nums) {
        if(nums == null || nums.length == 0) return 0;
        int n = nums.length;
        int[] arr = new int[n + 2];
        arr[0] = 1;
        arr[n + 1] = 1;
        for(int i = 0; i < n; i++){
            arr[i + 1] = nums[i];
        }

        int[][] dp = new int[n + 2][n + 2];


        return memoizedSearch(1, n, arr, dp);
    }

    private int memoizedSearch(int start, int end, int[] arr, int[][] dp){
        if(dp[start][end] != 0) return dp[start][end];

        int max = 0;
        for(int i = start; i <= end; i++){
            int cur = arr[start - 1] * arr[i] * arr[end + 1];
            int left = memoizedSearch(start, i - 1, arr, dp);
            int right = memoizedSearch(i + 1, end, arr, dp);

            max = Math.max(max, cur + left + right);
        }

        dp[start][end] = max;

        return max;
    }
}

Other answers for reference

*Divide and Conquer, Memoization, Recursive - (Runtime: 5 ms, faster than 99.18%)

(not including boundaries in the recursion - boundary balloons not bursted)

class Solution {
    public int maxCoins(int[] iNums) {
        int[] nums = new int[iNums.length + 2];
        int n = 1;
        for (int x : iNums) if (x > 0) nums[n++] = x;
        nums[0] = nums[n++] = 1;


        int[][] memo = new int[n][n];
        return burst(memo, nums, 0, n - 1);
    }

    public int burst(int[][] memo, int[] nums, int left, int right) {
        if (left + 1 == right) return 0;
        if (memo[left][right] > 0) return memo[left][right];
        int ans = 0;
        for (int i = left + 1; i < right; ++i)
            ans = Math.max(ans, nums[left] * nums[i] * nums[right] 
                           + burst(memo, nums, left, i) + burst(memo, nums, i, right));
        memo[left][right] = ans;
        return ans;
    }
}

Dynamic Programming - 6 ms , faster than 88.28%

public int maxCoins(int[] iNums) {
    int[] nums = new int[iNums.length + 2];
    int n = 1;
    for (int x : iNums) if (x > 0) nums[n++] = x;
    nums[0] = nums[n++] = 1;


    int[][] dp = new int[n][n];
    for (int k = 2; k < n; ++k)
        for (int left = 0; left < n - k; ++left) {
            int right = left + k;
            for (int i = left + 1; i < right; ++i)
                dp[left][right] = Math.max(dp[left][right], 
                nums[left] * nums[i] * nums[right] + dp[left][i] + dp[i][right]);
        }

    return dp[0][n - 1];
}

Reference

• [区间类DP总结](https://www.jianshu.com/p/4c462077f8f2\