memoization + tabulation

class Solution {
public:
int f(vector<int>& cuts,int s,int e,vector<vector<int>> &dp) {

    if(s>=e)  return 0;
    if(dp[s][e]!=-1) return dp[s][e];
    int mini=1e9;
     int cut=0;
     bool canCut=false;
    for(int i=0;i<cuts.size();i++) {

        if(cuts[i]<e&&cuts[i]>s) {
canCut=true;
            cut = (e-s)+f(cuts,s,cuts[i],dp) + f(cuts,cuts[i],e,dp);

            mini = min(cut,mini);
        }
    }
return  dp[s][e]=(canCut)? mini:0;
}

    int minCost(int n, vector<int>& cuts) {
        sort(cuts.begin(),cuts.end());
        //cout<<n<<endl;
        vector<vector<int>> dp(n+1,vector<int>(n+1,0));
        int cut=0;
      //  return f(cuts,0,n,dp);
        for(int i=n;i>=0;i--) {

            for(int j=i+1;j<=n;j++) {
                int mini = 1e9;
                bool canCut=false;


                    for(int k=0;k<cuts.size();k++) {
                           if(cuts[k]>=j) break;
        if(cuts[k]<j&&cuts[k]>i) {
            canCut=true;
            int cut = (j-i)+dp[i][cuts[k]] + dp[cuts[k]][j]; //f(cuts,s,cuts[i],dp) + f(cuts,cuts[i],e,dp);
            mini = min(cut,mini);
        }
    }
        dp[i][j] = (canCut)?mini:0;


            }
        }

  return dp[0][n];
    }
};