leetcode

Solution to some Leetcode problems written in C++

git clone git://git.dimitrijedobrota.com/leetcode.git

0312.cpp (796B)

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