【leetcode問題解】【また、ダイナミックプランニング】【H】【21.8】Burst Balloons

Given  n  balloons, indexed from  0  to  n-1 . Each balloon is painted with a number on it represented by array  nums . You are asked to burst all the balloons. If the you burst balloon  i  you will get  nums[left] * nums[i] * nums[right]  coins. Here  left  and  right  are adjacent indices of  i . After the burst, the  left  and  right  then becomes adjacent.
Find the maximum coins you can collect by bursting the balloons wisely.
Note:  (1) You may imagine  nums[-1] = nums[n] = 1 . They are not real therefore you can not burst them. (2) 0 ≤  n  ≤ 500, 0 ≤  nums[i]  ≤ 100
Example:
Given  [3, 1, 5, 8]
Return  167

    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

Credits: Special thanks to @dietpepsi for adding this problem and creating all test cases.
Subscribe
 to see which companies asked this question
【最も肝心なのは紫色です】この文のため、やっと保証することができて、それぞれ異なって動的に計画します
しかし、注意しなければならないのは、この時の過程は逆さまで、iは最初に爆発したのではなく、最後に爆発したのです.
この問題は当時,最後の操作状態と前の操作状態の関係を解析することによって行われた.ここでは最後のburstからこの問題を再考することができます.iが最後のburstであれば、その前に0~i-1,i+1~n-1の2つの区間の風船が除去され、しかも..最も重要なのは,iが最後に除去されるため,左右の2つの区間の過程が完全に分離され,すなわちサブ問題が見つかったことである.ここで見てみましょう
max(left)+left(左左後消去)*nums[i]*right(右最後消去)+max(right)
最後に,上記の式の各iについても,同様に左右の2つの区間についても列挙が必要であり,より小さな空間に絶えず区分される.両端に位置する数はnums[−1]=nums[n+1]=1のためであり、0が存在する場合、coinsは一切もたらされないため、直接除去することができることに注意されたい.
プログラミングの考え方:1.まず中に含まれている0を除去し、次にサイズを拡張し、最初に要素1を追加し、-1、n+1ビットを表します.
2.2次元配列を使用して、leftとrightの間の要素で得られる最大coins数を記録します.
3.leftは0からn-1、(拡張後はn-2)、rightはleftから異なる間隔の値であるべきである.注意、leftとrightは境界として機能します.
4.使用式:coins[left][right]=max(coins[left][right],coins[left][j]*nums[j]*coins[j][right])
5.最後に0,n−1を境界とするcoinsに徐々に拡張し、直接戻る.
dp[i][j] = max(dp[i][j], dp[i][x – 1] + nums[i – 1] * nums[x] * nums[j + 1] + dp[x + 1][j]);

class Solution(object):
    def boom(self,nums,res,left,right):
        #print left,right

        if right - left <= 1:
            return 0

        if res[left][right] >0:
            return res[left][right]
        maxx = 0
        for i in range(left+1,right):
            #print i
            maxx = max(maxx,nums[i]*nums[left]*nums[right] +
                self.boom(nums,res,left,i)+self.boom(nums,res,i,right))
        res[left][right] = maxx
        return res[left][right]

    def maxCoins(self, nums):
        #res = [1]
        res = [0]*(len(nums)+2)
        #res += [1]
        res1 = []

        for i in xrange(len(nums)+2):
            res1.append(res[:])

        res = res1[:]

        nums = [1] + nums +[1]
        nums = nums[:]
        return self.boom(nums,res,0,len(nums)-1)