LC: 1547 Minimum Cost To Cut Stick

#include <bits/stdc++.h>
using namespace std;


int minimumCost(int i, int j, vector<int> &paddedCuts, vector<vector<int> > &memo){
    // cout << i << " " << j << '\n';
    //no cuts available, so the cost of not cutting the stick is 0
    if(j - i <= 1){
        return 0;
    }

    if(memo[i][j] != -1){
        return memo[i][j];
    }

    int minIJ = INT_MAX;
    for(int k = i + 1; k < j; k++){
        int cutPosition = paddedCuts[k];

        int leftCost = minimumCost(i, k, paddedCuts, memo);
        int rightCost = minimumCost(k, j, paddedCuts, memo);
        minIJ = min(minIJ, leftCost + (paddedCuts[j] - paddedCuts[i]) + rightCost);
    }
    return memo[i][j] = minIJ;
 }


int minCuts(int length, vector<int> &cuts){
    sort(cuts.begin(), cuts.end());

    vector<int> paddedCuts;
    paddedCuts.push_back(0);
    paddedCuts.insert(paddedCuts.end(), cuts.begin(), cuts.end());
    paddedCuts.push_back(length);

    int n = paddedCuts.size();
    vector<vector<int> > memo(n, vector<int>(n, -1));
    return minimumCost(0, n - 1, paddedCuts, memo);
}

int main() {
    // your code goes here
    int n, k;
    cin >> n >> k;
    vector<int> cuts(k);
    for(int i = 0; i < k; i++){
        cin >> cuts[i];
    }

    cout << minCuts(n, cuts) << '\n';
}