My understanding of the n^3 dp solution, comments, explanation.


  • 8
    B

    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.

    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.
      Return when there is 0/1 non-zero numbers.

    2. create a dp matrix using the dimensionnonZeroNum + 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.

    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.

    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 startto 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]

        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 = idx-1;
        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<=nonZeroNum-len+1; start++){
                int end = start + len -1;
                int curMaxCoin = -1;
                for(int lastBurset = start; lastBurset<=end; lastBurset++){
                    curMaxCoin = Math.max(curMaxCoin, dp[start][lastBurset-1] + dp[lastBurset+1][end] + padded_arr[lastBurset]* padded_arr[start -1] * padded_arr[end+1]);
                }
                dp[start][end] = curMaxCoin;
            }
        }
        
        return dp[1][nonZeroNum];
        } 
    }

Log in to reply
 

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