# 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: 一、利用分治法Divide and Conquer结合记忆化memoization 二、或者利用区间型动态规划Dynamic Programming ### **Divide and Conquer with Memoization** > 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%) `start`, `end` boundary included (boundaries will be burst) `[start, ... i - 1, (i), i + 1 ... end]` ```java 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 ```java 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) ```java 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% ```java 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\\](https://www.jianshu.com/p/4c462077f8f2\)/)