312. Burst Balloons (Hard)

https://leetcode.com/problems/burst-balloons/

Given n balloons, indexed from 0 to n-1. Each balloon is painted with a number on it represented by array nums. You are asked to burst all the balloons. If the you burst balloon i you will get nums[left] * nums[i] * nums[right] coins. Here left and right are adjacent indices of i. After the burst, the left and right then becomes adjacent.

Find the maximum coins you can collect by bursting the balloons wisely.

Note:

  • You may imagine nums[-1] = nums[n] = 1. They are not real therefore you can not burst them.
  • 0 ≤ n ≤ 500, 0 ≤ nums[i] ≤ 100

Example:

Input: [3,1,5,8]
Output: 167 
Explanation: nums = [3,1,5,8] --> [3,5,8] -->   [3,8]   -->  [8]  --> []
             coins =  3*1*5      +  3*5*8    +  1*3*8      + 1*8*1   = 167

Solutions

public class Solution {

    // This problem is complicated, but it is a typical dynamic problem and worth trying.

    public int maxCoins(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }

        int len = nums.length;

        // max coins we can get when burst balloons in window x, y, or nums[x:y], where y is inclusive.
        int[][] dp = new int[len][len];

        // ws means window side
        for (int ws = 1; ws <= len; ws++) {

            // work out the max coins for given window size
            for (int start = 0; start <= len - ws; start++) {

                // ending index of search window
                int end = start + ws - 1;

                // At this point, we have dp for windows of which sizes are from 1 to ws - 1
                for (int i = start; i <= end; i++) {

                    // Suppose only i left, others in the window all burst. We need to plus the max
                    // coins of both sides when they burst.

                    // 1. max coins when burst all balloons in range [start, i-1];
                    // 2. max coins when burst all balloons in range [i + 1, end];

                    int coins = nums[i] * getValue(nums, start - 1) * getValue(nums, end + 1);

                    if (ws != 1) {
                        // i is the first one, we can only add right side
                        if (i == start) {
                            coins += dp[i + 1][end];
                        }
                        // i is the last one, we can only add left side
                        else if (i == end) {
                            coins += dp[start][i - 1];
                        }
                        // i is the middle, we can add both sides
                        else if (ws >= 3) {
                            coins += dp[start][i - 1] + dp[i + 1][end];
                        }
                    }


                    // Update the max coins if current schema is superior than previous.
                    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];
    }
}

Incorrect Solutions

class Solution {

    // Time exceeds the limit.

    // serves as cache to keep the best scores of computed nums
    Map<String, Integer> scoreMap = new HashMap<>();

    public int maxCoins(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }

        List<Integer> numList = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            numList.add(nums[i]);
        }

        return recurse(numList, numList.size());
    }

    private int recurse(List<Integer> nums, int len) {
        if (nums == null || len == 0) {
            return 0;
        }

        if (len == 1) {
            return 1 * nums.get(0) * 1;
        }

        // if nums already processed, return previous computed score
        if (scoreMap.containsKey(nums.toString())) {
            return scoreMap.get(nums.toString());
        }

        // keep the score of the best scheme
        int max = 0;

        for (int i = 0; i < len; i++) {
            // calculate if scores after burst balloon i
            int score = 0;

            if (i == 0) {
                score = 1 * nums.get(0) * nums.get(1);
            } else if (i == len - 1) {
                score = nums.get(len - 2) * nums.get(len - 1) * 1;
            } else {
                score = nums.get(i - 1) * nums.get(i) * nums.get(i + 1);
            }

            // save it for recover purpose
            int burstOne = nums.get(i);

            // shift elements after i forward by 1 step, simultaneously move element i to the end
            nums.remove(i);

            score += recurse(nums, len - 1);

            max = Math.max(max, score);

            // undo above shift process
            nums.add(i, burstOne);
        }

        // keep score of nums to cache
        scoreMap.put(nums.toString(), max);

        return max;
    }
}

References

Copyright © iovi.com 2017 all right reserved,powered by GitbookLast Modification: 2019-12-03 11:01:17

results matching ""

    No results matching ""