Minimum Cost to Cut a Stick LeetCode solution in C++

1
class Solution {
2
 public:
3
  long cutMin(int i, int j, vector<int> &c, vector<vector<int>> &dp) {
4
    if (i > j) return 0;
5
    if (dp[i][j] != -1) return dp[i][j];
6
    long mini = INT_MAX;
7
    for (int ind = i; ind <= j; ind++) {
8
      long cost = c[j + 1] - c[i - 1] + cutMin(i, ind - 1, c, dp) + cutMin(ind + 1, j, c, dp);
9
      mini = min(mini, cost);
10
    }
11
    return dp[i][j] = mini;
12
  }
13
  int minCost(int n, vector<int> &cuts) {
14
    int c = cuts.size();
15
    cuts.push_back(0);
16
    cuts.push_back(n);
17
    sort(cuts.begin(), cuts.end());
18
    vector<vector<int>> dp(c + 1, vector<int>(c + 1, -1));
19
    return cutMin(1, c, cuts, dp);
20
  }
21
};