312. Burst Balloons.md

312. Burst Balloons

---

leetcode-cn Daily Challenge on July 19th, 2020.

leetcode Daily Challenge on December 13th, 2020.

---

Difficulty : Hard

Related Topics : Divide and Conquer、Dynamic Programming

---

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

---

Solution

• mine
  • Java
    • DP-- got from the discuss Runtime: 9 ms, faster than 56.54%, Memory Usage: 39.3 MB, less than 7.95% of Java online submissions

      // O(N^3)time
      // O(N^2)space
      public int maxCoins(int[] nums) {
          int n = nums.length;
          int[] t = new int[n + 2];
          t[0] = t[n + 1] = 1;
          for (int i = 1; i <= n; i++) {
              t[i] = nums[i - 1];
          }
          // i + 1 < j
          // dp[i][j] = Max(dp[i][k] + dp[k][j] +  t[i] * t[k] * t[j])
          // k is the last one to bursted
          int[][] dp = new int[n + 2][n + 2];
          for (int i = n - 1; i >= 0; i--) {
              for (int j = i + 2; j < n + 2; j++) {
                  for (int k = i + 1; k < j; k++) {
                      int sum = t[i] * t[j] * t[k];
                      sum += dp[i][k] + dp[k][j];
                      dp[i][j] = Math.max(dp[i][j], sum);
                  }
              }
          }
          return dp[0][n + 1];
      }
      

    • DP Bottom-Up Runtime: 6 ms, faster than 95.33%, Memory Usage: 37.2 MB, less than 75.29% of Java online submissions

      // O(N^3)time
      // O(N^2)space
      public int maxCoins(int[] nums) {
          int n = nums.length + 2;
          int[] update = new int[n];
          update[0] = update[n - 1] = 1;
          System.arraycopy(nums, 0, update, 1, n -2);
      
          //dp[i][j] is mean the cost of burst balloons in (i, j) not [i, j]
          int[][] dp = new int[n][n];
          for(int len = 2; len < n; len++){
              for(int i = 0; i + len < n; i++){
                  int j = i + len;
                  for(int k = i + 1; k < j; k++){
                      int sum = dp[i][k] + dp[k][j] +  update[i] * update[j] * update[k];
                      dp[i][j] = Math.max(dp[i][j], sum);
                  }
              }
          }
          return dp[0][n - 1];
      }
      

---

• the most votes

• Divide and Conquer & Memorization Runtime: 10 ms, faster than 42.68%, Memory Usage: 39.2 MB, less than 8.43% of Java online submissions

  // O(N^3)time
  // O(N^2)space
  public int maxCoins(int[] iNums) {
      int[] nums = new int[iNums.length + 2];
      int n = 1;
      for (int x : iNums) if (x > 0) nums[n++] = x;
      nums[0] = nums[n++] = 1;
  
  
      int[][] memo = new int[n][n];
      return burst(memo, nums, 0, n - 1);
  }
  
  public int burst(int[][] memo, int[] nums, int left, int right) {
      if (left + 1 == right) return 0;
      if (memo[left][right] > 0) return memo[left][right];
      int ans = 0;
      for (int i = left + 1; i < right; ++i)
          ans = Math.max(ans, nums[left] * nums[i] * nums[right]
                  + burst(memo, nums, left, i) + burst(memo, nums, i, right));
      memo[left][right] = ans;
      return ans;
  }
  

• DP Runtime: 9 ms, faster than 56.54%, Memory Usage: 39.5 MB, less than 5.54% of Java online submissions

  // O(N^3)time
  // O(N^2)space
  public int maxCoins(int[] iNums) {
      int[] nums = new int[iNums.length + 2];
      int n = 1;
      for (int x : iNums) if (x > 0) nums[n++] = x;
      nums[0] = nums[n++] = 1;
  
  
      int[][] dp = new int[n][n];
      for (int k = 2; k < n; ++k)
          for (int left = 0; left < n - k; ++left) {
              int right = left + k;
              for (int i = left + 1; i < right; ++i)
                  dp[left][right] = Math.max(dp[left][right],
                    nums[left] * nums[i] * nums[right] + dp[left][i] + dp[i][right]);
          }
  
      return dp[0][n - 1];
  }
  

---