My understanding of the n^3 dp solution, comments, explanation.
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 s
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.\n\n 1. Burst all the zeros to avoid hassles. Pad 1 on the both sides of the array, that's my `padded_arr`, and I use `nonZeroNum ` to represent the actual non-zero numbers.\nReturn when there is 0/1 non-zero numbers.\n\n 2. create a dp matrix using the dimension`nonZeroNum + 2` x   `nonZeroNum + 2`, the reason is that, on the boundary condition, a.k.a, you are at the `1` on either end of the  `padded_arr`, those  `1` 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.\n\n 3. 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.\n\n 4. 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 from `start `to `end`, and that recursive element  `lastBurst` represents the last element to burst in this range. Since at that point of time, either both of   `start` and  `end` are already burst, or the `lastBurst` itself is  `start` or `end`, either way, the left and right neighbor should be `padded_arr[start -1] and padded_arr[end+1]`, rather than  `padded_arr[start] and padded_arr[end]`\n\n\n        public class Solution {\n        public int maxCoins(int[] nums) {\n        if (nums == null || nums.length == 0) return 0;\n    \n        int[] padded_arr = new int[nums.length+2];\n        int idx = 1;\n        padded_arr[0] = 1;\n        \n        for(int n:nums){\n            if(n != 0){\n                padded_arr[idx++] = n;\n            }\n        }\n        if(idx == 1) return 0;\n        if(idx == 2) return padded_arr[1];\n        \n        int nonZeroNum = idx-1;\n        padded_arr[idx++] = 1;\n        \n        //System.out.println("nonZeroNum = "+ nonZeroNum);\n\n\n        \n        int[][] dp = new int[nonZeroNum+2][nonZeroNum+2];\n        \n        for(int len = 1; len<=nums.length; len++){\n            for(int start = 1; start<=nonZeroNum-len+1; start++){\n                int end = start + len -1;\n                int curMaxCoin = -1;\n                for(int lastBurset = start; lastBurset<=end; lastBurset++){\n                    curMaxCoin = Math.max(curMaxCoin, dp[start][lastBurset-1] + dp[lastBurset+1][end] + padded_arr[lastBurset]* padded_arr[start -1] * padded_arr[end+1]);\n                }\n                dp[start][end] = curMaxCoin;\n            }\n        }\n        \n        return dp[1][nonZeroNum];\n        } \n    }
[]