Givennballoons, indexed from0ton-1. Each balloon is painted with a number on it represented by arraynums. You are asked to burst all the balloons. If the you burst ballooniyou will getnums[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 themaximumcoins you can collect by bursting the balloons wisely.

• You may imaginenums[-1] = nums[n] = 1. They are not real therefore you can not burst them.
• 0 ≤n≤ 500, 0 ≤nums[i]≤ 100

Have you met this question in a real interview?

Yes

Example

Given[4, 1, 5, 10]
Return270

nums = [4, 1, 5, 10] burst 1, get coins 4 * 1 * 5 = 20
nums = [4, 5, 10]    burst 5, get coins 4 * 5 * 10 = 200 
nums = [4, 10]       burst 4, get coins 1 * 4 * 10 = 40
nums = [10]          burst 10, get coins 1 * 10 * 1 = 10

Total coins 20 + 200 + 40 + 10 = 270

line 17 , result should be n - 2
line 16 second bool was written into flag

version 2 with init dp[i][i]
line 34 be careful of init value shoule be 0 instead of INT_MIN

class Solution {

public:

/\*\*

 \* @param nums a list of integer

 \* @return an integer, maximum coins

 \*/  

int maxCoins\(vector<int>& nums\) {

    // Write your code here

    if \(nums.empty\(\)\) {

        return 0;

    }

    nums.insert\(nums.begin\(\), 1\);

    nums.push\_back\(1\);

    int n = nums.size\(\);

    vector<vector<int> > dp\(n, vector<int>\(n, 0\)\);

    vector<vector<bool> > flag\(n, vector<bool>\(n, false\)\);

    // init

    for \(int i = 1; i < n - 1; ++i\) {

        dp\[i\]\[i\] = nums\[i - 1\] \* nums\[i\] \* nums\[i + 1\];

    }

    return search\(1, n - 2, nums, dp, flag\);

}

private:

int search\(int i, int j, vector<int>& nums, vector<vector<int> >& dp, vector<vector<bool> >& flag\)

{

    if \(flag\[i\]\[j\]\) {

        return dp\[i\]\[j\];

    }

    if \(i == j\) {

        flag\[i\]\[j\] = true;

        return dp\[i\]\[j\];

    }

    int best = 0;

    for \(int k = i; k <= j; ++k\) {

        int left  = search\(i, k - 1, nums, dp, flag\);

        int right = search\(k + 1, j, nums, dp, flag\);

        int mid   = nums\[i - 1\] \*  nums\[k\] \* nums\[j + 1\];

        best =  max\(best, left + right + mid\);

    }

    flag\[i\]\[j\] = true;

    dp\[i\]\[j\] = best;

    return best;

}

};