# My solution

• 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
};

``````

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