[LeetCode] Burst Ballons

Reference: https://leetcode.com/discuss/72216/share-some-analysis-and-explanations

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

public class Solution {     public int maxCoins(int[] nums) {         if (nums == null || nums.length == 0) return 0;         int[] ballons = new int[nums.length+2];         int index = 1;         for (int i = 0; i < nums.length; i++) {             if (nums[i] > 0) ballons[index++] = nums[i];         }         ballons[0] = ballons[index] = 1;         int[][] maximumPoints = new int[index+1][index+1];         for (int stepLength = 2; stepLength <= index; stepLength++) {             for (int left = 0; left <= index - stepLength; left++) {                 int right = left + stepLength;                 for (int i = left + 1; i < right; i++) {                     maximumPoints[left][right] = Math.max(maximumPoints[left][right], maximumPoints[left][i] + maximumPoints[i][right] + ballons[left]*ballons[i]*ballons[right]);                 }             }         }         return maximumPoints[0][index];     } }