leetcode

0 class Solution {

1 public:

2 int maxCoins(vector<int> &nums) const {

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

4 nums.push_back(1);

5

6 const int n = size(nums);

7 static int dp[303][303];

8

9 // dp[i][j]: coins obtained from bursting all the balloons between index i and j (not including i or

10 // j) dp[i][j] = max(nums[i] * nums[k] * nums[j] + dp[i][k] + dp[k][j]) (k in (i+1,j))

11

12 memset(dp, 0x00, sizeof(dp));

13 for (int d = 2; d < n; d++) {

14 for (int l = 0; l < n - d; l++) {

15 const int r = l + d;

16 for (int k = l + 1; k < r; k++) {

17 dp[l][r] = max(dp[l][r], nums[l] * nums[k] * nums[r] + dp[l][k] + dp[k][r]);

18 }

19 }

20 }

21

22 return dp[0][n - 1];

23 }

24 };