# 312 Burst Balloons
給一正整數矩陣，表示氣球上的$$數字，每爆破一個氣球總金額會增加 左邊氣球、自己、和右邊氣球的積，問爆破完所有氣球後能得到的最高金額為何。
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
Concept
這題如果照example的方式，從第一個爆破，一直加總到最後一個爆破，會很難切割成子問題。
關鍵點在於，從最後一個爆破開始加總。原因是：剩下的氣球金額和已爆破的氣球金額是不互相影響的。並且可以確定最後一個爆破的左右兩邊子矩陣不會相乘到。
子問題可以簡化為：在某子矩陣中(index i - j)，最後一個要爆破誰，可以將金額最大化？而該金額為多少？
Pseudocode
Main(nums):
Integer[][] dp = new Integer[n][n]
return maxCoins(dp, nums, 0, n-1)
maxCoins(dp, nums, start, end):
corner case check
define left, right
int i from start to end, // i represents the last balloon to pop
res = Math.max(res, left * nums[i] * right + maxCoins(nums, start, i - 1, dp) + maxCoins(nums, i + 1, end, dp));
return res
Code
class Solution {
public int maxCoins(int[] nums) {
/*
use dp[i][j] to record maxCoins from balloon i to balloon j
for each dp[start][end], go through start to end,
update result by max(result, nums[left]*nums[i]*nums[right] + maxCoins(start, i) +maxCoins(i+1, end))
final result would be dp[0][n]
*/
int n = nums.length;
Integer[][] dp = new Integer[n][n];
int result = maxCoins(0, n-1, dp, nums);
return result;
}
private int maxCoins(int start, int end, Integer[][] dp, int[] nums){
if(start > end){
return 0;
}
if(dp[start][end] != null){
return dp[start][end];
}
int n = nums.length;
int left = start == 0 ? 1 : nums[start-1];
int right = end == n-1 ? 1 : nums[end+1];
int result = Integer.MIN_VALUE;
for(int i=start; i<=end; i++){
result = Math.max(result, left*nums[i]*right + maxCoins(start, i-1, dp, nums) +maxCoins(i+1, end, dp, nums));
}
dp[start][end] = result;
return result;
}
}