Leetcode 312 burst ballons analysis - April 6, 2018 - 9:19 PM

Leetcode312 burstBallons analysis

https://blog.csdn.net/swartz2015/article/details/50561199

I like to study Leetcode 312: Burst balloons algorithm based on the above blog written in Chinese. What I like to do
is to go over the blog word by word, create a gist here. 

The idea is based on Leetcode discussion here:
https://leetcode.com/problems/burst-balloons/discuss/76228/share-some-analysis-and-explanations

Here are the notes written in Chinese, I will modify them in order for me to understand better. 

最初的想法：
  看到这个题目，很显然，第一反应不是用动态规划解决，而是回溯：
  
  ***动态规划里面的无后效性 ?***
  
  假设现在有n个气球，所以按照题意，若每踩一个气球定义为一个step，则需要 n 个 step 才能完成游戏。当进行到第 i 个 step 
的时候 ( i < n )，还剩下( n - i ) 个气球，也就是还需要 ( n - i ) step 才能完成游戏。用枚举，第一次踩气球，有 n 种踩法，
第 2 次踩气球有( n - 1 )中踩法，所以整个游戏有(n!)种完成途径，每个完成途径都可以计算出相应的获得的 coin，然后比较一下，
取出最大的即可。但是这个算法的复杂度为 O(n!)，无法接受。所以下面我们逐步优化。

通过观察可以知道。定义：现存的气球集合 N，被踩的气球集合 M。则 maxcoin(N)和 M 是无关的。也就是已经被踩的气球不会影响到
现存的气球的 maxcoin 计算(这里其实可以看到此问题符合动态规划里面的无后效性，具体可以参考知乎里面一个很好的回答：什么是动态规划？
动态规划的意义是什么？)。既然先被踩的气球不会影响后被踩的气球的 maxcoin，那我们可以选择先找出被踩两个气球时的 maxcoin，
被踩三个气球时的maxcoin，......，被踩 n 个气球时的 maxcoin，显然这是一个重叠子问题，并且以上描述显然是一个 DP 的 
bottom up思路。但是，计算被踩 k 个气球时的 maxcoin，需要枚举 C(n,k) 种情况，并进行比较，这导致子问题过多，也是就是
每个递归节点有过多的子节点，增加了计算复杂度，虽然比原始的 O(n!) 要好一点，但并不优于 O(2^n)，我们需要寻找具有二项式时间的算法。

更好的想法：

根据前面的分析，该问题可以分解为多个子问题，并逐一解决。于是，我们可以尝试是否可以用分治方法来解决呢？

这里需要明确可以用分治方法解决的问题以及可以用DP解决的问题的异同：

分治和DP都需要将原问题分解成小问题，然后逐一解决；不过分治方法的每个小问题都是不相关的，而DP的子问题则是重叠的(overlapping)。
可以参见wiki百科上面的解释：dynamic programming。

但是通过前面的分析也知道，之前描述的子问题都是重叠的 (比如你在计算踩 K 个气球时的 maxcoin，肯定会涉及到踩 K - 1 个气球时的结果，
这也是可以用 bottom up 的意义)，因此根本不能用分治方法来求解。自然的一个想法是，我们可不可以先把整体分割，再分别在被分割的各个
子整体中用 bottom up。这显然是可行的。不过问题在于怎么分割整体，因为整体的分割需要保证各个整体在后面的计算中要保持相互独立性。
比如对于[a1,a2,a3,a4,a5,a6,......,an]，将分割成两个子整体，分割点为k，则得到 N1 = [a1,a2,a3,....,a(k-1)], 
N2 = [a(k+1),a(k+2),.....,an]。这里分割点 k 的意义是踩破了第k个气球。于是把整体分成了两部分，问题在于，根据计算规则，k 气球
破了之后，a(k-1) 和 a(k+1)会变成相邻的，如果此时踩a(k-1)或者a(k+1)，则都会收到另一个子整体的影响，这样的话，两个子问题就不独立，
也就不能用分治了。所以关键的问题在于确定 k。

可以发现：

        N1和N2相互独立    <=>  k点为对于整体N的游戏时，最后一个被踩破的气球。

也就是k点被踩破之前，N1和N2重点的气球都不会相互影响。于是我们就成功构造了子问题。因此分治加dp就可以对问题进行求解了。

写一下状态传递方程：

dp[left][right] = max{dp[left][right] , nums[left] * nums[i] * nums[right]  +  nums[left] * nums[i]  +  nums[i] * nums[right]};

其中 left < i < right , dp[left][right] 即为当前子问题：第left和第right之间位置的气球的maxcoin。