Burst Ballons

思路：
一开始以为是stone game的马甲，结果情况更复杂。
transition: dp[i][j]=Max(dp[i][k-1]+dp[k+1][j]+nums[i-1]*nums[k]*nums[j+1])， i<=k<=j。dp[i][j]表示在i到j这个区间(inclusive)打气球得到的最大值。而k表示，最后一个打第k个气球的情况。比如[4,1,5,5]，最后一个打1，那么[4]和[5,5]都打完了，打1的时候的值就是1*1*1，不包括边界(exclusive)。

实现细节：
这里需要把第-1个和第n+1个2个为1的气球放进数组里。所以需要一个新的长度为n+2的数组。