[LC 312]. Burst Balloons

首先想到用图来表示一下这个过程:一共n步,第i步从n-i个气球中戳一个,例如[3,1,5,8]
start

|

| burst 0 | 1 | 2 |3
… coin: 315=15 …… coin: 40


| 0 |2 |3 | 0 | 1 |2
coin: 135 coin: 3
————- ……
| 2 |3
coin: 40 coin: 40


| 3 | 2
coin : 8 coin : 5

直接计算,time complexity是O(n!),但是发现一个规律:剩下的所有气球可以得到的max coin和已经burst的无关。例如,在[3,1,5,8]这个例子中,先burst3或1,剩下的都是[5,8],这个subarray得到的maxcoin和之前3和1哪个先burst无关,都是相同的,所以没必要重复计算,可以记录下来。

然后得到提示用divide and conquer,每次burst第i个,然后分成i以左和以右,两个subproblem。问题是左右虽然range虽然确定,但range的首位相邻的数字不确定,而且在算coin时需要。例如[3,1,5,8],先burst 1,左边剩下[3],3的左边是1右边变成了5;再burst 5,左边还是[3],3的左边还是1,但右边变成了8。这样虽然可以在recursion的时候,给function加上int head, int tail两个变量,但是会导致dp或者memoization不好实现。

然后是关键一步:换一种方法分割subproblem,采用top-down的思路 (reverse of bottom-up, which is above),若最后一个burst的是第i个,那么左右两个部分的head和tail都是确定的。例如[3,1,5,8],最后burst 1,左边是[3], 右边是[5,8], 无论倒数第二个burst哪个,head和tail都是1和1.
left             right
[ 1, 3,1,5,8, 1 ]
burst(int[] nums, int left, int right, int[][] dp) 是这个recursive function
其中:
for (i from left+1 to right-1) // last burst the ith balloon in the subproblem
ans = max(ans,
burst(nums, left, i, dp) +
burst(nums, i, right, dp) +
nums[left]nums[i]nums[right]) // head and tail for ith are known