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


  • 39
    A

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

    https://leetcode.com/discuss/72186/c-dynamic-programming-o-n-3-1100-ms-with-comments

    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];
    }
    

    }


  • 6
    2

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


  • 0
    R

    Thank you for a clear explanation.


  • 0
    P

    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];
    	}
    

  • 0
    M

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


  • 0

    I think recursive way is more intuitive.
    We divide the problem to two sub-problems.
    alt text
    花花酱 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];
        }
    }

Log in to reply
 

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