My solution


  • 0
    U

    Let S be the balloon set , S = {a1, a2, ... an} , A[i,j] is the optimize solution we found between balloon a[i] to a[j]. This as a typical dynamic programming problem that we should firstly find the subproblem of A[i,j].

    sub-problem

    We divide A[i,j] to A[i, k-1] U value(k) U A[k+1, j], then we should thing the meaning of value(k). Then we get:

    A[i,j] = max(A[i,j], A[i, k-1] + value(k) + A[k+1, j] )

    value(k) is money we get when we burst a[k]

    meaning of value(k)
    Meaning of A[i,j] is determined, but value(k) depends on the order .

    If a[k] is the first we burst, then value k depends on the successor burst, and value(k) is related to subproblems of A[i,j]. It seems doesn't work.

    If a[k] is the last one we burst, value(k) is determined: value(k) = nums[i-1]*nums[k] * nums[j+1] ,because a[i-1] and a[j+1]becomes adjacent when be burst a[k].

    Solution

    var maxCoins = function(nums) {
      A = []
      for(let i = 0; i < nums.length; i++) {
        for (let j = i; j >= 0; j-- ) {
          for (let k = j; k <= i; k++) {
            var p = nums[k] * (nums[i + 1] || 1) * (nums[j-1] || 1)
            A[j * nums.length + i] = Math.max(p +
                  (A[j * nums.length + k - 1] || 0)  + (A[(k+1) * nums.length + i] || 0),
                  A[j * nums.length + i] || 0)
    
          }
        }
      }
      return A[nums.length - 1] || 0
    };
    
    
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.