| 11 | } |
| 12 | |
| 13 | private int burst(int[] nums, int left, int right, int[][] dp) { |
| 14 | if (left > right) { |
| 15 | return 0; |
| 16 | } |
| 17 | if (dp[left][right] != 0) { |
| 18 | return dp[left][right]; |
| 19 | } |
| 20 | |
| 21 | for (int i = left; i <= right; i++) { |
| 22 | int coins = nums[i]; |
| 23 | |
| 24 | if (left - 1 >= 0) { |
| 25 | coins *= nums[left - 1]; |
| 26 | } |
| 27 | if (right + 1 < nums.length) { |
| 28 | coins *= nums[right + 1]; |
| 29 | } |
| 30 | |
| 31 | coins += |
| 32 | burst(nums, left, i - 1, dp) + burst(nums, i + 1, right, dp); |
| 33 | dp[left][right] = Math.max(dp[left][right], coins); |
| 34 | } |
| 35 | |
| 36 | return dp[left][right]; |
| 37 | } |
| 38 | } |