Java solution with explanation - 13ms


  • 0
    V

    If we go the route of choosing a balloon to burst and then write the recurrence relation then we cannot solve it by DP. The reason being after a chosen balloon is burst the input data changes its shape since neighbors change. The key to a DP solution(apart from having optimal subproblems) is non changing input.
    So the idea here is to choose a balloon to be burst last. Hence the recurrence relation stays same but instead will focus on choosing a balloon 'k' to be burst last. So for finding the max coins in a range of i - j, we choose all possible values of k(i <= k <= j) and use the intermediary subproblem solutions to find the max coins for [i,j]

        public int maxCoins(int[] nums) {
            if(nums==null || nums.length==0) return 0;
            
            int[] nums2 = new int[nums.length+2];
            nums2[0] = 1;
            nums2[nums2.length-1] = 1;
            for(int i=1;i<nums2.length-1;i++) {
                nums2[i] = nums[i-1];
            }
            int[][] dp = new int[nums2.length][nums2.length];
            dp[0][0] = 0;
            dp[nums2.length-1][nums2.length-1] = 0;
            
            for (int i = 1; i < nums2.length - 1; i++) {
    			for (int j = i; j >= 1; --j) {
    				for (int k = j; k <= i; k++) {
    					dp[j][i] = Math.max(dp[j][i],
    							dp[j][k - 1] + dp[k + 1][i] + (nums2[j - 1] * nums2[k] * nums2[i + 1]));
    				}
    			}
    		}
            
            return dp[1][nums2.length-2];
        }
    

Log in to reply
 

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