Easiest Java Solution

• The 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]`
• Imagine we burst index `i` at the end
• `[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`

Hope it helps!

``````public int maxCoins(int[] nums) {
int[][] dp = new int[nums.length][nums.length];
return maxCoins(nums, 0, nums.length - 1, dp);
}

public int maxCoins(int[] nums, int start, int end, int[][] dp) {
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, start, i - 1, dp) +
get(nums, i) * get(nums, start - 1) * get(nums, end + 1) +
maxCoins(nums, i + 1, end, dp);

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

public int get(int[] nums, int i) {
if (i == -1 || i == nums.length) {
return 1;
}
return nums[i];
}``````

• Great solution!
Would you just care to explain why is max = nums[start] before starting the for loop?

• @princessmaja I think It doesn't matter. If you initialize max to 0, it still works.

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