C++ 19ms 7 lines DP solution


  • 1
    int maxCoins(vector<int>& nums) {
            nums.insert(nums.begin(), 1), nums.insert(nums.end(), 1);   // add 1 at both first and last for convenience
            int len = nums.size(), dp[len][len]{};          // dp[l][r] is the max result of nums[l - r] inclusively
            
            for (int r = 1, end = len - 1; r < end; r++)
                for (int l = r; l > 0; l--)
                    for (int k = l; k <= r; k++)            // treat k as the last balloons bursted
                        dp[l][r] = max(dp[l][r], dp[l][k - 1] + nums[l - 1] * nums[k] * nums[r + 1] + dp[k + 1][r]);
    
            return dp[1][len - 2];
        }
    

Log in to reply
 

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