Honestly, I was a little confused when I read the most voted solution. I get the idea, but I had no clue how to fill in the dynamic matrix, so if you have the same confusion here, my comment might help you understand how to actually fill in the blanks.

Burst all the zeros to avoid hassles. Pad 1 on the both sides of the array, that's my
padded_arr
, and I usenonZeroNum
to represent the actual nonzero numbers.
Return when there is 0/1 nonzero numbers. 
create a dp matrix using the dimension
nonZeroNum + 2
xnonZeroNum + 2
, the reason is that, on the boundary condition, a.k.a, you are at the1
on either end of thepadded_arr
, those1
doesn't contribute to the coins. Since the element in the matrix is default to 0, you don't even have to internalize those elements. 
In this dp matrix, we only update half of the elements, and that's the half upper triangle, when we do the update, it's from left to right, and from bottom up, so the last element updated is the element in the up right corner.

Ok, now comes the important part... The
dp[start][end]
represents the maximum coins when you burst and only burst all the elements in the range of[start, end], 'start' and 'end' inclusive
. In the inner loop, recursive fromstart
toend
, and that recursive elementlastBurst
represents the last element to burst in this range. Since at that point of time, either both ofstart
andend
are already burst, or thelastBurst
itself isstart
orend
, either way, the left and right neighbor should bepadded_arr[start 1] and padded_arr[end+1]
, rather thanpadded_arr[start] and padded_arr[end]
public class Solution {
public int maxCoins(int[] nums) {
if (nums == null  nums.length == 0) return 0;
int[] padded_arr = new int[nums.length+2];
int idx = 1;
padded_arr[0] = 1;
for(int n:nums){
if(n != 0){
padded_arr[idx++] = n;
}
}
if(idx == 1) return 0;
if(idx == 2) return padded_arr[1];
int nonZeroNum = idx1;
padded_arr[idx++] = 1;
//System.out.println("nonZeroNum = "+ nonZeroNum);
int[][] dp = new int[nonZeroNum+2][nonZeroNum+2];
for(int len = 1; len<=nums.length; len++){
for(int start = 1; start<=nonZeroNumlen+1; start++){
int end = start + len 1;
int curMaxCoin = 1;
for(int lastBurset = start; lastBurset<=end; lastBurset++){
curMaxCoin = Math.max(curMaxCoin, dp[start][lastBurset1] + dp[lastBurset+1][end] + padded_arr[lastBurset]* padded_arr[start 1] * padded_arr[end+1]);
}
dp[start][end] = curMaxCoin;
}
}
return dp[1][nonZeroNum];
}
}