```
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];
}
```