Burst Balloons LeetCode solution in C++

1
class Solution {
2
 public:
3
  // topDown+memoization
4
  int solve(int i, int j, vector<int> &nums, vector<vector<int>> &dp) {
5
    if (i > j) return 0;
6
    if (dp[i][j] != -1) return dp[i][j];
7

8
    int maxcost = INT_MIN;
9
    for (int k = i; k <= j; k++) {
10
      int cost = nums[i - 1] * nums[k] * nums[j + 1] + solve(i, k - 1, nums, dp) +
11
                 solve(k + 1, j, nums, dp);
12
      maxcost = max(maxcost, cost);
13
    }
14
    return dp[i][j] = maxcost;
15
  }
16

17
  int maxCoins(vector<int> &nums) {
18
    nums.insert(nums.begin(), 1);
19
    nums.push_back(1);
20
    int n = nums.size();
21
    vector<vector<int>> dp(n + 1, vector<int>(n + 1, -1));
22
    return solve(1, n - 2, nums, dp);
23
  }
24

25
  // bottomUp dp
26
  int maxCoins(vector<int> &nums) {
27
    // including the nums[-1] == 1 and nums[n] == 1
28
    int n = nums.size();
29
    nums.insert(nums.begin(), 1);
30
    nums.push_back(1);
31
    vector<vector<int>> dp(nums.size() + 1, vector<int>(nums.size() + 1, 0));
32

33
    for (int len = 1; len <= n; ++len)
34
      for (int left = 1; left <= n - len + 1; ++left) {
35
        int right = left + len - 1;
36
        for (int k = left; k <= right; ++k)
37
          dp[left][right] = max(dp[left][right], nums[left - 1] * nums[k] * nums[right + 1] +
38
                                                     dp[left][k - 1] + dp[k + 1][right]);
39
      }
40
    return dp[1][n];
41
  }
42
};