# Java DP solution with detailed explanation, O(n^3)

• This solution is inspired by The_Duck with his C++ solution

However, I would give an explanation based on my own understanding.

The basic idea is that we can find the maximal coins of a subrange by trying every possible final burst within that range. Final burst means that we should burst balloon i as the very last one and burst all the other balloons in whatever order. dp[i][j] means the maximal coins for range [i...j]. In this case, our final answer is dp[0][nums.length - 1].

When finding the maximal coins within a range [start...end], since balloon i is the last one to burst, we know that in previous steps we have already got maximal coins of range[start .. i - 1] and range[i + 1 .. start], and the last step is to burst ballon i and get the product of balloon to the left of i, balloon i, and ballon to the right of i. In this case, balloon to the left/right of i is balloon start - 1 and balloon end + 1. Why? Why not choosing other balloon in range [0...start - 1] and [end + 1...length] because the maximal coins may need other balloon as final burst?

In my opinion, it's because this subrange will only be used by a larger range when it's trying for every possible final burst. It will be like [larger start.....start - 1, [start .. end] end + 1/ larger end], when final burst is at index start - 1, the result of this sub range will be used, and at this moment, start - 1 will be there because it's the final burst and end + 1 will also be there because is out of range. Then we can guarantee start - 1 and end + 1 will be there as adjacent balloons of balloon i for coins. That's the answer for the question in previous paragraph.

``````public class Solution {
public int maxCoins(int[] nums) {
if (nums == null || nums.length == 0) return 0;

int[][] dp = new int[nums.length][nums.length];
for (int len = 1; len <= nums.length; len++) {
for (int start = 0; start <= nums.length - len; start++) {
int end = start + len - 1;
for (int i = start; i <= end; i++) {
int coins = nums[i] * getValue(nums, start - 1) * getValue(nums, end + 1);
coins += i != start ? dp[start][i - 1] : 0; // If not first one, we can add subrange on its left.
coins += i != end ? dp[i + 1][end] : 0; // If not last one, we can add subrange on its right
dp[start][end] = Math.max(dp[start][end], coins);
}
}
}
return dp[0][nums.length - 1];
}

private int getValue(int[] nums, int i) { // Deal with num[-1] and num[num.length]
if (i < 0 || i >= nums.length) {
return 1;
}
return nums[i];
}
``````

}

• First thsnks for your share the code .I think we could think this way,

``````for (int i = start; i <= end; i++) {
int coins = nums[i] * getValue(nums, start - 1) * getValue(nums, end + 1);
coins += i != start ? dp[start][i - 1] : 0; // If not first one, we can add subrange on its left.
coins += i != end ? dp[i + 1][end] : 0; // If not last one, we can add subrange on its right
dp[start][end] = Math.max(dp[start][end], coins);
}
``````

why we use start-1and end+1。Because for each "i" ballon in the subrange [start.....end],we will burst " i " at
the end in this subrange.In this situation ,at the end ,the "i" ballon's left and right ballon must be start-1and end+1.So we try different i and record the max one to be the maximal coins of this subrange in the var dp[start][end].

• Thank you for a clear explanation.

• Same logic but easy calculation and understanding.

``````public int maxCoins(int[] nums) {// DP based solution. O(N^2) space and
// O(N^3) run time.
if (nums.length == 0)
return 0;
int n = nums.length;
int[] iNums = new int[n + 2];
iNums[0] = 1; // add 1 in the beginning.
for (int i = 0; i < n; i++)
iNums[i + 1] = nums[i];
iNums[iNums.length - 1] = 1; // add trailing 1.

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

for (int len = 1; len <= n; len++) {
for (int i = 1; i + len < n + 2; i++) {
for (int j = i; j < i + len; j++) {
int val = iNums[i - 1] * iNums[j] * iNums[i + len]; // easy calculation.
memo[i][i + len - 1] = Math.max(memo[i][i + len - 1], // previous subrange + current val + next subrange.
val + memo[i][j - 1] + memo[j + 1][i + len - 1]);
}
}
}
return memo[1][n];
}
``````

• thanks a lot! your codes are a lot better and ez understanding than the top voted answer!

• I think recursive way is more intuitive.
We divide the problem to two sub-problems.

花花酱 LeetCode 312. Burst Balloons

``````class Solution {
public int maxCoins(int[] nums) {
int n = nums.length;
int[] newnums = new int[n + 2];
newnums[0] = 1; newnums[n + 1] = 1;
for(int i = 0; i < n; i++){
newnums[i + 1] = nums[i];
}
int[][] C = new int[n + 2][n + 2];
return helper(newnums, C, 1, n);
}

int helper(int[] nums, int[][] C, int s, int e){
if(s > e) return 0;
if(C[s][e] > 0){
return C[s][e];
}
for(int i = s; i <= e; i++){
int v = nums[s - 1] * nums[i] * nums[e + 1] + helper(nums, C, s, i - 1) + helper(nums, C, i + 1, e);
C[s][e] = Math.max(C[s][e], v);
}
return C[s][e];
}
}``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.