Burst Balloons 312

Description

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: (1) You may imagine nums[-1] = nums[n] = 1. They are not real therefore you can not burst them. (2) 0 ≤ n ≤ 500, 0 ≤ nums[i] ≤ 100

Example:

Given [3, 1, 5, 8]

Return 167

nums = [3,1,5,8] --> [3,5,8] -->   [3,8]   -->  [8]  --> []

coins = 315 + 358 + 138 + 181 = 167 Credits: Special thanks to @dietpepsi for adding this problem and creating all test cases.

Hint

DP + divide & conquer usually, we use divide and conquer to divide from the middle but for this problem since each time when we burst a balloon, it will influence the remain res so we can assure from ending, to lock the two side balloons and assure each balloon is the last one to be burst.

Method

[3, 1,5,8] -> [1, 3 ,1, 5, 8, 1] for 3 is the last one : [1, 3] [1, 5, 8, 1] -> recursive [1, 5, 8, 1]-> [1, 5][8, 1] [1,3,1] [5, 8 , 1] dp[i][j]: burst balloons from i - j to earn the max init: left = 0 right = n dp[i][j] = 0; transit : for i : left + 1 -( right - 1) dp[left][right] = math.max(n[left] n[right] n[i] + dp[left][i] + dp[i][right]);

Time & Space

o(n^3)

Code

public class Solution {
    public int maxCoins(int[] nums) {
           if (nums == null){
               return 0;
           }
           int len = nums.length;
           int[] balloons = new int[len + 2];
           balloons[0] = 1;
           balloons[len + 1] = 1;
           for (int i = 1; i < len + 1; i++){
                balloons[i] = nums[i - 1];
           }

           int[][] dp = new int[len + 2][len + 2];
           for (int k = 2; k < len + 2; k++){
                for (int left = 0; left < len + 2 - k; left++){
                     int right = left + k;
                     for (int i = left + 1; i < right; i++){
                          dp[left][right] = Math.max(dp[left][right], balloons[left]*balloons[i]*balloons[right] + dp[left][i] + dp[i][right]);
                     }
                }
           }
           return dp[0][len + 1];
    }
}