Cost to Cut a Chocolate

The basic idea is to find all the cuttings orders and select the minimum out of them. If we have chocolate of starting index (say, ‘startIdx’) and ending index (‘endIdx’), we divide it into two parts by cutting it at any given point. We check all the places we can cut, take the minimum of them, and add the current length of the chocolate. The base case will be when the size of chocolate is less than equal to 1 as it cannot be cut further into smaller pieces.
 

Here is the algorithm :

1. Insert 0 and ‘N’ in the ‘CUTS’ array to include the chocolate length.
2. Sort the ‘CUTS’ array.
3. Call the HELPER function to find the minimum cost and return the value returned by the function.

HELPER(‘N’, ‘CUTS’, ‘startIdx’, ‘endIdx’)  (where ‘startIdx’ and ‘endIdx’ and the positions we do the cuts)

1. Base case:
   • Check if ‘endIdx’ - ‘startIdx’ is smaller than or equal to 1.
     • Return 0.
2. Create a variable (say, ‘totalCost’) to store the total cost and initialize it with some large value.
3. Run a loop from ‘startIdx’ + 1 to ‘endIdx’ (say, iterator ‘i’) to cut the ‘ith’ position.
   • Recursively call the HELPER function and update the value of ‘endIdx’ to ‘i’ and store the value returned by the function in a variable (say, ‘COST1’).
   • Recursively call the HELPER function and update the value of ‘startIdx’ to ‘i’ and store the value returned by the function in a variable (say, ‘COST2’).
   • Update ‘totalCost’ with the minimum of ‘totalCost’ and sum of ‘COST1’ and ‘COST2’.
4. Add (‘CUTS[endIdx]’ - ‘CUTS[startIdx]’) to the ‘totalCost’ to include the length of the chocolate.
5. Return ‘totalCost’.

The approach is similar to the previous approach. In this approach, we just store the recursive calls of the function to avoid repeated recursive calls. 

How do we know recursive calls are being repeated?

Let ‘N’ be 3 and the ‘CUTS’ array be [1, 2].

We call recursion to calculate the cost for, say, indices (0, 1).

Now let’s change the order of cuts to [2, 1]. We first call recursion on, say, indices (0, 2). We further divide this chocolate into (0, 1) and (1, 2).

We can see (0, 1) is being repeated again. For large inputs, there will be more extra recursive calls. To avoid this, we memoize our approach and save the results in an array (say, ‘DP’).

Here is the algorithm :
 

1. Insert 0 and ‘N’ in the ‘CUTS’ array to include the chocolate length.
2. Sort the ‘CUTS’ array.
3. Create a 2D array (say, ‘DP’) of the size ‘CUTS’ and initialize it with -1.
4. Call the HELPER function to find the minimum cost and return the value returned by the function.
    

HELPER(‘N’, ‘CUTS’, ‘startIdx’, ‘endIdx’, ‘DP’)  (where ‘startIdx’ and ‘endIdx’ and the positions we do the cuts)

1. Base case:
   • Check if ‘endIdx’ - ‘startIdx’ is smaller than or equal to 1.
     • Return 0.
2. Check if ‘DP[startIdx][endIdx]’ is not equal to -1.
   • Return ‘DP[startIdx][endIdx]’.
3. Create a variable (say, ‘totalCost’) to store the total cost and initialize it with some large value.
4. Run a loop from ‘startIdx’ + 1 to ‘endIdx’ (say, iterator ‘i’) to cut the ‘ith’ position.
   • Recursively call the HELPER function and update the value of ‘endIdx’ to ‘i’ and store the value returned by the function in a variable (say, ‘COST1’).
   • Recursively call the HELPER function and update the value of ‘startIdx’ to ‘i’ and store the value returned by the function in a variable (say, ‘COST2’).
   • Update ‘totalCost’ with the minimum of ‘totalCost’ and sum of ‘COST1’ and ‘COST2’.
5. Add (‘CUTS[endIdx]’ - ‘CUTS[startIdx]’) to the ‘totalCost’ to include the length of the chocolate.
6. Store the value of ‘totalCost’ at ‘DP[startIdx][endIdx]’ and return it.

The basic idea is to avoid recursion to reduce the space used in the recursive stack. We iteratively solve the problem. We calculate answers for cases where the number of cuts between the starting index and ending index of chocolate is 1, we calculate the answer for the cases where the gap between starting and ending is 2. We create an array (say, ‘DP’) initialized with 0 to store the results, where ‘DP[i][j]’ stores the minimum cost of cutting when we cut the chocolate starting from length ‘CUTS[i]’ and ‘CUTS[j]’.

Here is the algorithm :
 

1. Insert 0 and ‘N’ in the ‘CUTS’ array to include the chocolate length.
2. Sort the ‘CUTS’ array.
3. Create a 2D array (say, ‘DP’) of the size of ‘CUTS’ and initialize it with 0.
4. Run a loop from 2 to the size of ‘CUTS’ (say, iterator ‘gap’).
   • Run a loop from 0 to the size of ‘CUTS’ (say, iterator ‘i’) and from ‘gap’ to the size of ‘CUTS’ (say, iterator ‘j’) simultaneously.
     • Create a variable (say, ‘totalCost’) to store the cost and initialize it with a large number.
     • Run a loop from ‘i’ + 1 to ‘j’ (say, iterator ‘k’).
       • Update ‘totalCost’ with minimum of ‘totalCost’ and sum of ‘DP[i][k]’ and ‘DP[k][j]’.
     • Update ‘DP[i][j]’ with sum of ‘totalCost’ and (‘CUTS[j] - ‘CUTS[i]’).
5. Return ‘DP[0][C - 1]’.