Space Complexity: O(N), We are using an auxiliary recursion stack space O(N).1d:T499f,

If we draw the recursion tree, we will see that there are overlapping subproblems. Hence the DP approaches can be applied to the recursive solution.

In order to convert a recursive solution to memoization the following steps will be taken:

Declare a dp array of size [c+1][c+1]: As there are two changing parameters in the recursive solution, 'i' and 'j'. The value of 'i' and 'j' ranges from 0 to c. Therefore, we need 2D dp array.

The dp array stores the calculations of subproblems. Initialize dp array with -1, to indicate that no subproblem has been solved yet.

While encountering an overlapping subproblem: When we come across a subproblem, for which the dp array has value other than -1, it means we have found a subproblem which has been solved before hence it is an overlapping subproblem. No need to calculate it's value again just retrieve the value from dp array and return it.
Store the value of subproblem: Whenever, a subproblem is enocountered and it is not solved yet(the value at this index will be -1 in the dp array), store the calculated value of subproblem in the array.

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

class Solution{
private:
    // Function to calculate the minimum cost incurred
    int func(int i, int j, vector<int> &cuts, vector<vector<int>> &dp) {
        /* Base case: If i is greater than 
        j, there are no cuts to consider.*/
        if (i > j) {
            return 0;
        }
        
        //Check if the subproblem is already solved
        if (dp[i][j] != -1) {
            return dp[i][j];
        }
        
        int mini = INT_MAX;

        for (int ind = i; ind <= j; ind++) {
            /* Calculate the cost for
            making a cut at position 'ind'.*/
            int ans = cuts[j + 1] - cuts[i - 1] + func(i, ind - 1, cuts, dp) + func(ind + 1, j, cuts, dp);

            mini = min(mini, ans);
        }
        //Return the result
        return dp[i][j] = min