Minimum Cost to Merge Stones LeetCode solution in C++

1
class Solution {
2
 public:
3
#define LIM 32
4
  vector<int> prefixSum = {0};
5
  int dp[LIM][LIM][LIM];
6
  int solve(vector<int> &stones, int start, int end, int k) {
7
    // Base Case: Invalid Index or For single element answer is always 0
8
    if (start >= end) return 0;
9
    int cost = INT_MAX;
10
    if (dp[start][end][k] != -1) return dp[start][end][k];
11
    for (int i = start; i < end; i = i + k - 1)
12
      cost = min(cost, solve(stones, start, i, k) + solve(stones, i + 1, end, k));
13
    if ((end - start) % (k - 1) == 0) cost += prefixSum[end + 1] - prefixSum[start];
14
    return dp[start][end][k] = cost;
15
  }
16
  int mergeStones(vector<int> &stones, int k) {
17
    int n = stones.size();
18
    if ((n - 1) % (k - 1) != 0) return -1;
19
    for (int i : stones) prefixSum.push_back(prefixSum.back() + i);
20
    for (int i = 0; i < LIM; i++)
21
      for (int j = 0; j < LIM; j++)
22
        for (int k = 0; k < LIM; k++) dp[i][j][k] = -1;
23
    return solve(stones, 0, n - 1, k);
24
  }
25
};