Easiest Java Solution


  • 7

    The subproblems are overlapped. So we can use divide and conquer + cache.

    • Balloons 0, 1, ..., n - 1
    • What is the max value if we burst all of them [0, n - 1]?
    • Let's first consider bursting [start, end]
    • Imagine we burst index i at the end
    • [start, ... i - 1, (i), i + 1 ... end]
    • Before the end, we already bursted [start, i - 1] and [i + 1, end]
    • Before the end, boundaries start - 1, i, end + 1 are always there
    • This helps us calculate coins without worrying about details inside [start, i - 1] and [i + 1, end]
    • So the range can be divided into
    • start - 1, maxCoin(start, i - 1), i, maxCoins(i + 1, end), end + 1

    Hope it helps!

    public int maxCoins(int[] nums) {
        int[][] dp = new int[nums.length][nums.length];
        return maxCoins(nums, 0, nums.length - 1, dp);
    }
    
    public int maxCoins(int[] nums, int start, int end, int[][] dp) {
        if (start > end) {
            return 0;
        }
        if (dp[start][end] != 0) {
            return dp[start][end];
        }
        int max = nums[start];
        for (int i = start; i <= end; i++) {
            int val = maxCoins(nums, start, i - 1, dp) + 
                      get(nums, i) * get(nums, start - 1) * get(nums, end + 1) + 
                      maxCoins(nums, i + 1, end, dp);
                      
            max = Math.max(max, val);
        }
        dp[start][end] = max;
        return max;
    }
    
    public int get(int[] nums, int i) {
        if (i == -1 || i == nums.length) {
            return 1;
        }
        return nums[i];
    }

  • 0
    P

    Great solution!
    Would you just care to explain why is max = nums[start] before starting the for loop?


  • 1
    I

    @princessmaja I think It doesn't matter. If you initialize max to 0, it still works.


Log in to reply
 

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