Minimum cost to cut the stick

We need to minimize the cost incurred to cut the stick. Whenever we make a cut, we are changing the length of the stick which in turn decides the cost. Therefore the order in which we make the cuts changes the total cost. As discussed in previous problem, whenever the order of solving the problem comes into play, we can think in terms of Partition DP.

Rules to solve a problem on partition dp:

Marking the array with i,j: We are given a stick of size N and the CUTS array. Every element of the CUTS array represents the marking at which one cut needs to be made. When we make a cut, we are dividing the stick into two different parts.

Ideally, we would want to place the i, and j pointers at both ends of the CUTS array and try to solve the problem recursively, which we will eventually do. But we need to modify the given array. We will first discuss the need for a modification and then we will learn about the exact modification required. We have the following example:

Now, we try to place i and j on both ends of the CUTS array. Suppose we want to cut the stick at CUTS[0], i.e marking 3, then we will divide the bigger problem ( stick of length 7) into two smaller problems ( sticks of length 3 and 4) and solve these sub-problems independently (as we are looking for a recursive solution). Now the problem which arises is that when we make a cut at marking 3, we also need to think of something to distribute the CUTS array. This means we need to define separate i, and j pointers for each subproblem. We can try breaking the CUTS array in the following way:

Try out all Partitions: As we have figured out the logic for marking the i, and j pointers, we will move to the partitioning loop. We can simply write a for loop(say ind) starting from i to j, The problem is being broken in the following manner:

/*It is a pseudocode and it not tied to
any specific programming language*/

f(i, j){
    for(int ind = i; ind <= j; ind++){
        ans = cuts[j+1] - cuts[i-1] + f(i, ind-1, cuts) + f(ind+1, j, cuts)
    }
}

Note: We are breaking the left subproblem to f(i,ind-1) rather than f(i,ind) because we have already made a cut at CUTS[ind] and we don't want to consider it twice.

Base Case: As i <=j, we can say that when i>j this is not a valid partition so we can return 0.
Return the best possible answer to the two partitions: We know that the recursive functions along with the base case will get us the answer to the subproblems, but still, there is some work to do. We need to find the cost incurred to make the cut that is breaking the stick at CUTS[ind]. The cost incurred will be the length of the stick on which the cut is being made. We only have the CUTS array to figure it out, let's see how.

If we push 0 and N to both ends of the CUTS array:

Then CUTS[j+1] - CUTS[i-1] will always give us the correct length of the stick on which the cut is being made. Readers are advised to dry run with some other examples too to understand this.

/*It is a pseudocode and it not tied to
any specific programming language*/

f(i, j){
    mini = INT_MAX
    for(int ind = i; ind <= j; ind++){
        ans = cuts[j+1] - cuts[i-1] + f(i, ind-1, cuts) + f(ind+1, j, cuts)
        mini = min(mini, ans)
    }
}

To summarize:

Sort the CUTS array.
Append 0 and N at both ends of the CUTS array.
Convert the problem to a recursive function marked by two pointers i and j.
Use a partitioning loop to try all partitions.
Return the answer in which the partition gives the minimum cost.

#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) {
        /* Base case: If i is greater than 
        j, there are no cuts to consider.*/
        if (i > j) {
            return 0;
        }
        
        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) + func(ind + 1, j, cuts);

            mini = min(mini, ans);
        }
        //Return the result
        return mini;
    }
public:
    // Function to compute the minimum cost
    int minCost(int n, vector<int> &cuts) {
        int c = cuts.size();
        /* Modify the cuts array by adding 0 
        at the beginning and 'n' at the end.*/
        cuts.push_back(n);
        cuts.insert(cuts.begin(), 0);
        sort(cuts.begin(), cuts.end());

       // Call the recursive function to find minimum cost.
       return func(1, c, cuts);
    }
};

int main() {
    vector<int> cuts = {3, 5, 1, 4};
    int n = 7;
    
    //Create an instance of Solution class
    Solution sol;
    
    cout << "The minimum cost incurred is: " << sol.minCost(n, cuts) << endl;

    return 0;
}

import java.util.*;

class Solution {
    // Function to calculate the minimum cost incurred
    private int func(int i, int j, int[] cuts) {
        /* Base case: If i is greater than
        j, there are no cuts to consider.*/
        if (i > j) {
            return 0;
        }

        int mini = Integer.MAX_VALUE;

        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) + func(ind + 1, j, cuts);

            mini = Math.min(mini, ans);
        }
        // Return the result
        return mini;
    }

    // Function to compute the minimum cost
    public int minCost(int n, List<Integer> cuts) {
        int c = cuts.size();
        /* Convert List<Integer> to int[] */
        int[] newCuts = new int[c + 2];
        newCuts[0] = 0;
        for (int i = 0; i < c; i++) {
            newCuts[i + 1] = cuts.get(i);
        }
        newCuts[c + 1] = n;
        Arrays.sort(newCuts);

        // Call the recursive function to find minimum cost.
        return func(1, c, newCuts);
    }

    public static void main(String[] args) {
        List<Integer> cuts = new ArrayList<>();
        cuts.add(3);
        cuts.add(5);
        cuts.add(1);
        cuts.add(4);
        int n = 7;

        // Create an instance of Solution class
        Solution sol = new Solution();

        System.out.println("The minimum cost incurred is: " + sol.minCost(n, cuts));
    }
}
class Solution:
    # Function to calculate the minimum cost incurred
    def func(self, i, j, cuts):
        """ Base case: If i is greater than
        j, there are no cuts to consider."""
        if i > j:
            return 0

        mini = float('inf')

        for ind in range(i, j + 1):
            """ Calculate the cost for 
            making a cut at position 'ind'."""
            ans = cuts[j + 1] - cuts[i - 1] + self.func(i, ind - 1, cuts) + self.func(ind + 1, j, cuts)

            mini = min(mini, ans)
        
        # Return the result
        return mini

    # Function to compute the minimum cost
    def minCost(self, n, cuts):
        c = len(cuts)
        """ Modify the cuts array by adding 0 
        at the beginning and 'n' at the end."""
        cuts = [0] + sorted(cuts) + [n]

        # Call the recursive function to find minimum cost.
        return self.func(1, c, cuts)

if __name__ == "__main__":
    cuts = [3, 5, 1, 4]
    n = 7

    # Create an instance of Solution class
    sol = Solution()

    print("The minimum cost incurred is:", sol.minCost(n, cuts))
class Solution {
    // Function to calculate the minimum cost incurred
    func(i, j, cuts) {
        /* Base case: If i is greater than
        j, there are no cuts to consider.*/
        if (i > j) {
            return 0;
        }

        let mini = Number.MAX_VALUE;

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

            mini = Math.min(mini, ans);
        }
        // Return the result
        return mini;
    }

    // Function to compute the minimum cost
    minCost(n, cuts) {
        let c = cuts.length;
        /* Modify the cuts array by adding 0
        at the beginning and 'n' at the end.*/
        cuts = [0, ...cuts.sort((a, b) => a - b), n];

        // Call the recursive function to find minimum cost.
        return this.func(1, c, cuts,);
    }
}

const cuts = [3, 5, 1, 4];
const n = 7;

// Create an instance of Solution class
const sol = new Solution();

console.log("The minimum cost incurred is:", sol.minCost(n, cuts));

Complexity Analysis:

Time Complexity: Exponential.

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

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] = mini;
    }
public:
    // Function to compute the minimum cost
    int minCost(int n, vector<int> &cuts) {
        int c = cuts.size();
        /* Modify the cuts array by adding 0 
        at the beginning and 'n' at the end.*/
        cuts.push_back(n);
        cuts.insert(cuts.begin(), 0);
        sort(cuts.begin(), cuts.end());
        
        // Create a DP table to store calculated values.
        vector<vector<int>> dp(c + 1, vector<int>(c + 1, -1));

       // Call the recursive function to find minimum cost.
       return func(1, c, cuts, dp);
    }
};

int main() {
    vector<int> cuts = {3, 5, 1, 4};
    int n = 7;
    
    //Create an instance of Solution class
    Solution sol;
    
    cout << "The minimum cost incurred is: " << sol.minCost(n, cuts) << endl;

    return 0;
}

import java.util.*;

class Solution {
    // Function to calculate the minimum cost incurred
    private int func(int i, int j, int[] cuts, 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 = Integer.MAX_VALUE;

        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 = Math.min(mini, ans);
        }
        // Return the result
        return dp[i][j] = mini;
    }

    // Function to compute the minimum cost
    public int minCost(int n, List<Integer> cuts) {
        int c = cuts.size();
        /* Convert List<Integer> to int[] */
        int[] newCuts = new int[c + 2];
        newCuts[0] = 0;
        for (int i = 0; i < c; i++) {
            newCuts[i + 1] = cuts.get(i);
        }
        newCuts[c + 1] = n;
        Arrays.sort(newCuts);

        // Create a DP table to store calculated values.
        int[][] dp = new int[c + 1][c + 1];
        for (int[] row : dp) {
            Arrays.fill(row, -1);
        }

        // Call the recursive function to find minimum cost.
        return func(1, c, newCuts, dp);
    }

    public static void main(String[] args) {
        List<Integer> cuts = new ArrayList<>();
        cuts.add(3);
        cuts.add(5);
        cuts.add(1);
        cuts.add(4);
        int n = 7;

        // Create an instance of Solution class
        Solution sol = new Solution();

        System.out.println("The minimum cost incurred is: " + sol.minCost(n, cuts));
    }
}
class Solution:
    # Function to calculate the minimum cost incurred
    def func(self, i, j, cuts, 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]

        mini = float('inf')

        for ind in range(i, j + 1):
            """ Calculate the cost for 
            making a cut at position 'ind'."""
            ans = cuts[j + 1] - cuts[i - 1] + self.func(i, ind - 1, cuts, dp) + self.func(ind + 1, j, cuts, dp)

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

    # Function to compute the minimum cost
    def minCost(self, n, cuts):
        c = len(cuts)
        """ Modify the cuts array by adding 0 
        at the beginning and 'n' at the end."""
        cuts = [0] + sorted(cuts) + [n]

        # Create a DP table to store calculated values.
        dp = [[-1] * (c + 2) for _ in range(c + 2)]

        # Call the recursive function to find minimum cost.
        return self.func(1, c, cuts, dp)

if __name__ == "__main__":
    cuts = [3, 5, 1, 4]
    n = 7

    # Create an instance of Solution class
    sol = Solution()

    print("The minimum cost incurred is:", sol.minCost(n, cuts))
class Solution {
    // Function to calculate the minimum cost incurred
    func(i, j, cuts, 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];
        }

        let mini = Number.MAX_VALUE;

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

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

    // Function to compute the minimum cost
    minCost(n, cuts) {
        let c = cuts.length;
        /* Modify the cuts array by adding 0
        at the beginning and 'n' at the end.*/
        cuts = [0, ...cuts.sort((a, b) => a - b), n];

        // Create a DP table to store calculated values.
        let dp = Array.from({ length: c + 1 }, () => Array(c + 1).fill(-1));

        // Call the recursive function to find minimum cost.
        return this.func(1, c, cuts, dp);
    }
}

const cuts = [3, 5, 1, 4];
const n = 7;

// Create an instance of Solution class
const sol = new Solution();

console.log("The minimum cost incurred is:", sol.minCost(n, cuts));

Complexity Analysis:

Time Complexity: O(N*N*N), There are N*N states and we explicitly run a loop inside the function which will run for N times, therefore at max ‘N*N*N’ new problems will be solved.

Space Complexity:O(N*N) + O(N). We are using an auxiliary recursion stack space O(N) and a 2D array O(N*N).

In order to convert a recursive code to tabulation code, we try to convert the recursive code to tabulation and here are the steps:

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.
Handle the base case: We knew in the recursive code the base case was when i > j, it meant that there are no cuts to consider. So, to cover this case we can initialize the entire dp array with 0.
Next, memoization is a top-down approach, whereas tabulation is bottom-up. Our changing parameters i and j will change in opposite directions, i.e i will change from c→1 and j will change from 1→ c.
After that, copy down the recursive logic inside the nested loops to get the tabulation code.

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

class Solution{
public:
    // Function to compute the minimum cost incurred
    int minCost(int n, vector<int> &cuts) {
        int c = cuts.size();
        
        /* Modify the cuts array by adding 0
        at the beginning and 'n' at the end.*/
        cuts.push_back(n);
        cuts.insert(cuts.begin(), 0);
        sort(cuts.begin(), cuts.end());

        // Create a DP table to store calculated values.
        vector<vector<int>> dp(c + 2, vector<int>(c + 2, 0));

        for (int i = c; i >= 1; i--) {
            for (int j = 1; j <= c; j++) {
                if (i > j) continue;

                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] + dp[i][ind - 1] + dp[ind + 1][j];

                    mini = min(mini, ans);
                }
                //Store the minimum value in dp table
                dp[i][j] = mini;
            }
        }
        //Return the result
        return dp[1][c];
    }
};

int main() {
    vector<int> cuts = {3, 5, 1, 4};
    int n = 7;
    
    //Create an instance of Solution class
    Solution sol;
    
    cout << "The minimum cost incurred is: " << sol.minCost(n, cuts) << endl;

    return 0;
}

import java.util.*;

class Solution {
    // Function to compute the minimum cost incurred
    public int minCost(int n, List<Integer> cuts) {
        int c = cuts.size();
        
        /* Modify the cuts array by adding 0
        at the beginning and 'n' at the end.*/
        cuts.add(n);
        cuts.add(0);
        Collections.sort(cuts);

        // Create a DP table to store calculated values.
        int[][] dp = new int[c + 2][c + 2];

        for (int i = c; i >= 1; i--) {
            for (int j = 1; j <= c; j++) {
                if (i > j) continue;

                int mini = Integer.MAX_VALUE;

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

                    mini = Math.min(mini, ans);
                }
                // Store the minimum value in dp table
                dp[i][j] = mini;
            }
        }
        // Return the result
        return dp[1][c];
    }

    public static void main(String[] args) {
        List<Integer> cuts = new ArrayList<>(Arrays.asList(3, 5, 1, 4));
        int n = 7;

        // Create an instance of Solution class
        Solution sol = new Solution();

        System.out.println("The minimum cost incurred is: " + sol.minCost(n, cuts));
    }
}
class Solution:
    # Function to compute the minimum cost incurred
    def minCost(self, n, cuts):
        c = len(cuts)
        
        """ Modify the cuts array by adding 0 
        at the beginning and 'n' at the end."""
        cuts.append(n)
        cuts.append(0)
        cuts.sort()

        # Create a DP table to store calculated values.
        dp = [[0] * (c + 2) for _ in range(c + 2)]

        for i in range(c, 0, -1):
            for j in range(1, c + 1):
                if i > j:
                    continue

                mini = float('inf')

                for ind in range(i, j + 1):
                    """ Calculate the cost for
                    making a cut at position 'ind'."""
                    ans = cuts[j + 1] - cuts[i - 1] + dp[i][ind - 1] + dp[ind + 1][j]

                    mini = min(mini, ans)
                
                # Store the minimum value in dp table
                dp[i][j] = mini
        
        # Return the result
        return dp[1][c]

if __name__ == "__main__":
    cuts = [3, 5, 1, 4]
    n = 7

    # Create an instance of Solution class
    sol = Solution()

    print("The minimum cost incurred is:", sol.minCost(n, cuts))
class Solution {
    // Function to compute the minimum cost incurred
    minCost(n, cuts) {
        let c = cuts.length;
        
        /* Modify the cuts array by adding 0 
        at the beginning and 'n' at the end.*/
        cuts.push(n);
        cuts.push(0);
        cuts.sort((a, b) => a - b);

        // Create a DP table to store calculated values.
        let dp = Array.from({ length: c + 2 }, () => Array(c + 2).fill(0));

        for (let i = c; i >= 1; i--) {
            for (let j = 1; j <= c; j++) {
                if (i > j) continue;

                let mini = Number.MAX_VALUE;

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

                    mini = Math.min(mini, ans);
                }
                // Store the minimum value in dp table
                dp[i][j] = mini;
            }
        }
        // Return the result
        return dp[1][c];
    }
}

const cuts = [3, 5, 1, 4];
const n = 7;

// Create an instance of Solution class
const sol = new Solution();

console.log("The minimum cost incurred is:", sol.minCost(n, cuts));

Complexity Analysis:

Time Complexity:O(N*N*N), There are 2 variables i and j, therefore, N*N states and we explicitly run a loop inside the function which will run for N times, therefore at max ‘N*N*N’ new problems will be solved.

Space Complexity:O(N*N), We are using a 2D array O(N*N).

Problem List

Minimum cost to cut the stick

Examples:

Constraints

Hints

Company Tags

Editorial

Rules to solve a problem on partition dp:

To summarize:

Complexity Analysis:

Complexity Analysis:

Complexity Analysis:

Frequently Occurring Doubts

Interview Followup Questions

Notes

Code