O(n^3) Java Solution Sharing


  • 0
    // https://www.youtube.com/watch?v=IFNibRVgFBo
    public class Solution {
        public int maxCoins(int[] nums) {
            if(nums == null || nums.length == 0) return 0;
            int[][] dp = new int[nums.length][nums.length];
            // len is the range of calculation
            for(int len=1; len<=nums.length; len++) {
                // i is the index of leftmost balloon of this calculation range
                for(int i=0; i<=nums.length-len; i++) {
                    // j is the index of rightmost balloon of this calculation range
                    int j = i + len - 1;
                    // k is the index of last balloon to be bursted
                    for(int k=i; k<=j; k++) {
                        // based on the statement, nums[-1] = nums[n] = 1 even though they are not real
                        int leftValue = 1, rightValue = 1;
                        if(i != 0) leftValue = nums[i-1];
                        if(j != nums.length - 1) rightValue = nums[j+1];
                        
                        // whether there is any balloon bursted before or after k
                        int before = 0, after = 0;
                        if(k != i) before = dp[i][k-1];
                        if(k != j) after = dp[k+1][j];
                        
                        dp[i][j] = Math.max(dp[i][j], before + leftValue * nums[k] * rightValue + after);
                    }
                }
            }
            return dp[0][nums.length-1];
        }
    }
    

Log in to reply
 

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