Minimum cost to cut a stick of length n

Given a wooden stick of length n units. The stick is labeled from 0 to n. We are also given an integer array cuts[], where each element cuts[i] represents the position along the stick at which we can make a cut.

Each cut costs the length of the stick being cut, and after every cut, the stick is divided into two smaller sticks. We can perform the cuts in any order, determine the minimum total cost required to perform all cuts.

Examples:

Input: n = 10, cuts[] = [2, 4, 7]
Output: 20
Explanation: If we cut the stick in the order [4, 2, 7], it will give the minimum total cost.

Input: n = 8, cuts[] = [1, 6, 3, 5]
Output: 19
Explanation: If we cut the stick in the order [3, 6, 1, 5], it will give the minimum total cost.

[Naive Approach 1] Using Recursion

In this problem, we have multiple possibilities for where we can make the first cut. Once we cut the stick at a certain position, it divides into two smaller parts and each of those parts again becomes a smaller version of the same problem. Because we have to explore all possible ways of cutting and find the one that gives the minimum total cost, using recursion becomes a very natural and intuitive choice here.

The idea is like this - first, we include 0 and n in the cuts array because these represent the two ends of the stick. This helps define every segment clearly between two valid cut positions. Since the order of cuts matters, and we also need to easily calculate the length of any segment, we sort the cuts array. Sorting allows us to directly find the current stick’s length using the difference (right - left).
After sorting, we explore all possible ways to make a cut between left and right. If we make a cut at position cuts[i], the stick splits into two smaller subproblems - one from left to cuts[i] and another from cuts[i] to right. We then solve both subproblems recursively to find their minimum cost.

We will stop the recursion when there are no more possible cuts between left and right, that means when the segment length becomes ≤ 1. In that case, no further cuts are possible, so the cost is 0.

//Driver Code Starts
#include <iostream>
#include<vector>
#include<climits>
#include<algorithm>
using namespace std;
//Driver Code Ends


int minCostRec(int left, int right, vector<int> &cuts) {
    
    // Base case
    if (right - left <= 1)
        return 0;

    int minCost = INT_MAX;

    // Explore all possible cuts between left and right
    for (int i = left + 1; i < right; i++) {
        int cost = cuts[right] - cuts[left] + minCostRec(left, i, cuts)
                 + minCostRec(i, right, cuts);

        minCost = min(minCost, cost);
    }

    // If no valid cut found, cost is 0
    return (minCost == INT_MAX) ? 0 : minCost;
}

int minCutCost(int n, vector<int> &cuts) {
    
    // Add boundaries 0 and n to represent stick ends
    cuts.push_back(0);
    cuts.push_back(n);

    // Sort to ensure segments are in proper order
    sort(cuts.begin(), cuts.end());
    return minCostRec(0, cuts.size() - 1, cuts);
}


//Driver Code Starts
int main() {
    int n = 10;
    vector<int> cuts = {2, 4, 7};

    cout << minCutCost(n, cuts);
    return 0;
}

//Driver Code Ends

//Driver Code Starts
import java.util.ArrayList;
import java.util.Collections;

public class GFG {
//Driver Code Ends


    static int minCostRec(int left, int right, ArrayList<Integer> cutsList) {
        // Base case
        if (right - left <= 1)
            return 0;

        int minCost = Integer.MAX_VALUE;

        // Explore all possible cuts between left and right
        for (int i = left + 1; i < right; i++) {
            int cost = cutsList.get(right) - cutsList.get(left)
                     + minCostRec(left, i, cutsList)
                     + minCostRec(i, right, cutsList);

            minCost = Math.min(minCost, cost);
        }

        // If no valid cut found, cost is 0
        return (minCost == Integer.MAX_VALUE) ? 0 : minCost;
    }

    static int minCutCost(int n, int[] cuts) {
        ArrayList<Integer> cutsList = new ArrayList<>();
        for (int cut : cuts)
            cutsList.add(cut);

        // Add boundaries 0 and n to represent stick ends
        cutsList.add(0);
        cutsList.add(n);

        // Sort to ensure segments are in proper order
        Collections.sort(cutsList);

        return minCostRec(0, cutsList.size() - 1, cutsList);
    }


//Driver Code Starts
    public static void main(String[] args) {
        int n = 10;
        int[] cuts = {2, 4, 7};

        System.out.println(minCutCost(n, cuts));
    }
}

//Driver Code Ends

def minCostRec(left, right, cuts):
    
    # Base case
    if right - left <= 1:
        return 0

    minCost = float('inf')

    # Explore all possible cuts between left and right
    for i in range(left + 1, right):
        cost = cuts[right] - cuts[left] + minCostRec(left, i, cuts) + minCostRec(i, right, cuts)
        minCost = min(minCost, cost)

    # If no valid cut found, cost is 0
    return 0 if minCost == float('inf') else minCost


def minCutCost(n, cuts):
    
    # Add boundaries 0 and n to represent stick ends
    cuts.append(0)
    cuts.append(n)

    # Sort to ensure segments are in proper order
    cuts.sort()
    return minCostRec(0, len(cuts) - 1, cuts)



#Driver Code Starts

if __name__ == "__main__":
    n = 10
    cuts = [2, 4, 7]
    print(minCutCost(n, cuts))

#Driver Code Ends

//Driver Code Starts
using System;
using System.Collections.Generic;

class GFG
{
//Driver Code Ends

    static int minCostRec(int left, int right, List<int> cutsList)
    {
        // Base case
        if (right - left <= 1)
            return 0;

        int minCost = int.MaxValue;

        // Explore all possible cuts between left and right
        for (int i = left + 1; i < right; i++)
        {
            int cost = cutsList[right] - cutsList[left]
                       + minCostRec(left, i, cutsList)
                       + minCostRec(i, right, cutsList);

            minCost = Math.Min(minCost, cost);
        }

        // If no valid cut found, cost is 0
        return (minCost == int.MaxValue) ? 0 : minCost;
    }

    static int minCutCost(int n, int[] cuts)
    {
        List<int> cutsList = new List<int>(cuts);

        // Add boundaries 0 and n to represent stick ends
        cutsList.Add(0);
        cutsList.Add(n);

        // Sort to ensure segments are in proper order
        cutsList.Sort();

        return minCostRec(0, cutsList.Count - 1, cutsList);
    }


//Driver Code Starts
    static void Main()
    {
        int n = 10;
        int[] cuts = { 2, 4, 7 };

        Console.WriteLine(minCutCost(n, cuts));
    }
}

//Driver Code Ends

function minCostRec(left, right, cuts) {
    
    // Base case
    if (right - left <= 1) return 0;

    let minCost = Infinity;

    // Explore all possible cuts between left and right
    for (let i = left + 1; i < right; i++) {
        let cost = cuts[right] - cuts[left]
                 + minCostRec(left, i, cuts)
                 + minCostRec(i, right, cuts);
        minCost = Math.min(minCost, cost);
    }

    // If no valid cut found, cost is 0
    return minCost === Infinity ? 0 : minCost;
}

function minCutCost(n, cuts) {
    
    // Add boundaries 0 and n to represent stick ends
    cuts.push(0);
    cuts.push(n);

    // Sort to ensure segments are in proper order
    cuts.sort((a, b) => a - b);
    return minCostRec(0, cuts.length - 1, cuts);
}



//Driver Code Starts
//Driver Code
let n = 10;
let cuts = [2, 4, 7];
console.log(minCutCost(n, cuts));

//Driver Code Ends

20

Time Complexity: O(k!), where k is the number of cuts because we explore all possible orders of cuts.
Auxiliary Space: O(k) – due to the recursion stack.

[Expected Approach - 1] Using Memoization (Top Down)

In the recursive approach, we noticed that many subproblems are solved multiple times. For example, the cost to cut a segment [left, right] is computed repeatedly whenever this segment appears in different recursive paths. To avoid this repeated work, we use memoization (DP).

The idea is simple: whenever we compute the minimum cost for a segment [left, right], we store the result in a DP table.
We can create a 2D DP table where dp[i][j] represents the minimum cost to cut the stick between the i-th and j-th cut positions. Before performing the recursion for a segment, we check if dp[i][j] has already been computed. If yes, we return it directly; otherwise, we compute and store it. This reduces the exponential recursive solution to a polynomial time solution.

//Driver Code Starts
#include <iostream>
#include <vector>
#include <climits>
#include <algorithm>
using namespace std;
//Driver Code Ends


int minCostRec(int left, int right, vector<int> &cuts, vector<vector<int>> &dp) {
    
    // Base case
    if (right - left <= 1)
        return 0;

    // Return stored result if already computed
    if (dp[left][right] != -1)
        return dp[left][right];

    int minCost = INT_MAX;

    // Explore all possible cuts between left and right
    for (int i = left + 1; i < right; i++) {
        int cost = cuts[right] - cuts[left] + minCostRec(left, i, cuts, dp)
                 + minCostRec(i, right, cuts, dp);

        minCost = min(minCost, cost);
    }

    return dp[left][right] = (minCost == INT_MAX) ? 0 : minCost;
}

int minCutCost(int n, vector<int> &cuts) {
    
    // Add boundaries 0 and n to represent stick ends
    cuts.push_back(0);
    cuts.push_back(n);

    // Sort to ensure segments are in proper order
    sort(cuts.begin(), cuts.end());

    int sz = cuts.size();
    
    //for storing the previously computed result 
    vector<vector<int>> dp(sz, vector<int>(sz, -1));

    return minCostRec(0, sz - 1, cuts, dp);
}


//Driver Code Starts
int main() {
    int n = 10;
    vector<int> cuts = {2, 4, 7};

    cout << minCutCost(n, cuts);
    return 0;
}

//Driver Code Ends

//Driver Code Starts
import java.util.ArrayList;  
import java.util.Arrays;     
import java.util.Collections;

public class GFG {
//Driver Code Ends


    static int minCostRec(int left, int right, int[] cuts, int[][] dp) {
        
        // Base case
        if (right - left <= 1)
            return 0;

        // Return stored result if already computed
        if (dp[left][right] != -1)
            return dp[left][right];

        int minCost = Integer.MAX_VALUE;

        // Explore all possible cuts between left and right
        for (int i = left + 1; i < right; i++) {
            int cost = cuts[right] - cuts[left] + minCostRec(left, i, cuts, dp)
                     + minCostRec(i, right, cuts, dp);

            minCost = Math.min(minCost, cost);
        }

        return dp[left][right] = (minCost == Integer.MAX_VALUE) ? 0 : minCost;
    }

    static int minCutCost(int n, int[] cuts) {
        
        // Create ArrayList to add boundaries 0 and n
        ArrayList<Integer> arrayList = new ArrayList<>();
        for (int c : cuts)
            arrayList.add(c);

        arrayList.add(0);
        arrayList.add(n);

        // Sort to ensure segments are in proper order
        Collections.sort(arrayList);

        int sz = arrayList.size();
        int[] sortedCuts = new int[sz];
        for (int i = 0; i < sz; i++)
            sortedCuts[i] = arrayList.get(i);

        // for storing the previously computed result 
        int[][] dp = new int[sz][sz];
        for (int[] row : dp)
            Arrays.fill(row, -1);

        return minCostRec(0, sz - 1, sortedCuts, dp);
    }


//Driver Code Starts
    public static void main(String[] args) {
        int n = 10;
        int[] cuts = {2, 4, 7};
        System.out.println(minCutCost(n, cuts));
    }
}

//Driver Code Ends

#Driver Code Starts
import sys

#Driver Code Ends


def minCostRec(left, right, cuts, dp):
    
    # Base case
    if right - left <= 1:
        return 0

    # Return stored result if already computed
    if dp[left][right] != -1:
        return dp[left][right]

    minCost = float('inf')

    # Explore all possible cuts between left and right
    for i in range(left + 1, right):
        cost = cuts[right] - cuts[left] + minCostRec(left, i, cuts, dp) + minCostRec(i, right, cuts, dp)
        minCost = min(minCost, cost)

    dp[left][right] = 0 if minCost == float('inf') else minCost
    return dp[left][right]


def minCutCost(n, cuts):
    
    # Add boundaries 0 and n to represent stick ends
    cuts.append(0)
    cuts.append(n)

    # Sort to ensure segments are in proper order
    cuts.sort()

    sz = len(cuts)
    
    # for storing the previously computed result 
    dp = [[-1 for _ in range(sz)] for _ in range(sz)]

    return minCostRec(0, sz - 1, cuts, dp)


#Driver Code Starts

if __name__ == "__main__":
    n = 10
    cuts = [2, 4, 7]
    print(minCutCost(n, cuts))

#Driver Code Ends

//Driver Code Starts
using System;
using System.Collections.Generic;

public class GFG
{
//Driver Code Ends

    static int minCostRec(int left, int right, int[] cuts, int[,] dp)
    {
        // Base case
        if (right - left <= 1)
            return 0;

        // Return stored result if already computed
        if (dp[left, right] != -1)
            return dp[left, right];

        int minCost = int.MaxValue;

        // Explore all possible cuts between left and right
        for (int i = left + 1; i < right; i++)
        {
            int cost = cuts[right] - cuts[left] + minCostRec(left, i, cuts, dp)
                     + minCostRec(i, right, cuts, dp);

            minCost = Math.Min(minCost, cost);
        }

        dp[left, right] = (minCost == int.MaxValue) ? 0 : minCost;
        return dp[left, right];
    }

    static int minCutCost(int n, int[] cuts)
    {
        // Create List to add boundaries 0 and n
        List<int> list = new List<int>(cuts);
        list.Add(0);
        list.Add(n);

        // Sort to ensure segments are in proper order
        list.Sort();

        int sz = list.Count;
        int[] sortedCuts = list.ToArray();

        // for storing the previously computed result 
        int[,] dp = new int[sz, sz];
        for (int i = 0; i < sz; i++)
            for (int j = 0; j < sz; j++)
                dp[i, j] = -1;

        return minCostRec(0, sz - 1, sortedCuts, dp);
    }


//Driver Code Starts
    public static void Main()
    {
        int n = 10;
        int[] cuts = { 2, 4, 7 };
        Console.WriteLine(minCutCost(n, cuts));
    }
}

//Driver Code Ends

function minCostRec(left, right, cuts, dp) {
    
    // Base case
    if (right - left <= 1)
        return 0;

    // Return stored result if already computed
    if (dp[left][right] !== -1)
        return dp[left][right];

    let minCost = Number.MAX_SAFE_INTEGER;

    // Explore all possible cuts between left and right
    for (let i = left + 1; i < right; i++) {
        let cost = cuts[right] - cuts[left] + minCostRec(left, i, cuts, dp)
                 + minCostRec(i, right, cuts, dp);

        minCost = Math.min(minCost, cost);
    }

    dp[left][right] = (minCost === Number.MAX_SAFE_INTEGER) ? 0 : minCost;
    return dp[left][right];
}

function minCutCost(n, cuts) {
    
    // Add boundaries 0 and n to represent stick ends
    cuts.push(0);
    cuts.push(n);

    // Sort to ensure segments are in proper order
    cuts.sort((a, b) => a - b);

    const sz = cuts.length;

    // for storing the previously computed result 
    const dp = Array.from({ length: sz }, () => Array(sz).fill(-1));

    return minCostRec(0, sz - 1, cuts, dp);
}



//Driver Code Starts
// Driver Code
const n = 10;
const cuts = [2, 4, 7];
console.log(minCutCost(n, cuts));

//Driver Code Ends

20

Time complexity: O(k³), where k is the number of cuts.
Auxiliary Space: O(k²)

[Expected Approach - 2] Using Bottom-Up (Tabulation)

In the memoization approach, we used recursion along with a DP table to store results of subproblems so that we don’t recompute them again and again. Although this reduced the number of repeated calculations, it still relied on recursive calls, which can lead to extra stack usage and overhead.
To overcome this, we switch to a completely iterative (bottom-up) method known as Tabulation.

The idea is similar, here instead of making recursive calls, we iteratively build the DP table from smaller segments to larger ones. We start with the smallest possible segments (where no cuts can be made), and for these, the cost is naturally 0. Then, we gradually move to larger segments - at each step, combining the results of smaller parts that have already been computed and stored in the DP table.
This ensures that whenever we calculate the cost for a bigger segment, the results of all its sub-segments are readily available. By the end, the DP table contains the minimum cost for every possible segment.

//Driver Code Starts
#include <iostream>
#include <vector>
#include <climits>
#include <algorithm>
using namespace std;
//Driver Code Ends


int minCutCost(int n, vector<int> &cuts) {

    // Add boundaries 0 and n to represent stick ends
    cuts.push_back(0);
    cuts.push_back(n);

    // Sort to ensure segments are in proper order
    sort(cuts.begin(), cuts.end());

    int sz = cuts.size();

    vector<vector<int>> dp(sz, vector<int>(sz, 0));

    for (int len = 2; len < sz; len++) {
        for (int left = 0; left + len < sz; left++) {
            int right = left + len;
            int minCost = INT_MAX;

            // Explore all possible cuts between left and right
            for (int i = left + 1; i < right; i++) {
                int cost = cuts[right] - cuts[left] + dp[left][i] + dp[i][right];
                minCost = min(minCost, cost);
            }

            // Store the minimum cost for this segment
            dp[left][right] = (minCost == INT_MAX) ? 0 : minCost;
        }
    }

    // Final result is the cost to cut the full stick (0 to sz - 1)
    return dp[0][sz - 1];
}


//Driver Code Starts
int main() {
    int n = 10;
    vector<int> cuts = {2, 4, 7};

    cout << minCutCost(n, cuts);
    return 0;
}

//Driver Code Ends

//Driver Code Starts
import java.util.ArrayList;
import java.util.Collections;

class GFG {
//Driver Code Ends


    static int minCutCost(int n, int[] cuts) {

        ArrayList<Integer> list = new ArrayList<>();
        for (int c : cuts) list.add(c);

        // Add boundaries 0 and n to represent stick ends
        list.add(0);
        list.add(n);

        // Sort to ensure segments are in proper order
        Collections.sort(list);

        int sz = list.size();
        int[][] dp = new int[sz][sz];

        for (int len = 2; len < sz; len++) {
            for (int left = 0; left + len < sz; left++) {
                int right = left + len;
                int minCost = Integer.MAX_VALUE;

                // Explore all possible cuts between left and right
                for (int i = left + 1; i < right; i++) {
                    int cost = list.get(right) - list.get(left)
                             + dp[left][i] + dp[i][right];
                    minCost = Math.min(minCost, cost);
                }

                // Store the minimum cost for this segment
                dp[left][right] = (minCost == Integer.MAX_VALUE) ? 0 : minCost;
            }
        }

        // Final result is the cost to cut the full stick (0 to sz - 1)
        return dp[0][sz - 1];
    }


//Driver Code Starts
    public static void main(String[] args) {
        int n = 10;
        int[] cuts = {2, 4, 7};
        System.out.println(minCutCost(n, cuts));
    }
}

//Driver Code Ends

def minCutCost(n, cuts):
    
    # Add boundaries 0 and n to represent stick ends
    cuts.append(0)
    cuts.append(n)

    # Sort to ensure segments are in proper order
    cuts.sort()

    sz = len(cuts)
    
    # Initialize dp table with all zeros
    dp = [[0] * sz for _ in range(sz)]

    for length in range(2, sz):
        for left in range(sz - length):
            right = left + length
            minCost = float('inf')

            # Explore all possible cuts between left and right
            for i in range(left + 1, right):
                cost = cuts[right] - cuts[left] + dp[left][i] + dp[i][right]
                minCost = min(minCost, cost)

            # Store the minimum cost for this segment
            dp[left][right] = 0 if minCost == float('inf') else minCost

    # Final result is the cost to cut the full stick (0 to sz - 1)
    return dp[0][sz - 1]



#Driver Code Starts

if __name__ == "__main__":
    n = 10
    cuts = [2, 4, 7]
    print(minCutCost(n, cuts))

#Driver Code Ends

//Driver Code Starts
using System;
using System.Collections.Generic;

class GFG {
//Driver Code Ends


    static int minCutCost(int n, int[] cuts) {

        List<int> list = new List<int>(cuts);

        // Add boundaries 0 and n to represent stick ends
        list.Add(0);
        list.Add(n);

        // Sort to ensure segments are in proper order
        list.Sort();

        int sz = list.Count;
        int[,] dp = new int[sz, sz];

        for (int len = 2; len < sz; len++) {
            for (int left = 0; left + len < sz; left++) {
                int right = left + len;
                int minCost = int.MaxValue;

                // Explore all possible cuts between left and right
                for (int i = left + 1; i < right; i++) {
                    int cost = list[right] - list[left] + dp[left, i] + dp[i, right];
                    minCost = Math.Min(minCost, cost);
                }

                // Store the minimum cost for this segment
                dp[left, right] = (minCost == int.MaxValue) ? 0 : minCost;
            }
        }

        // Final result is the cost to cut the full stick (0 to sz - 1)
        return dp[0, sz - 1];
    }


//Driver Code Starts
    static void Main() {
        int n = 10;
        int[] cuts = {2, 4, 7};

        Console.WriteLine(minCutCost(n, cuts));
    }
}

//Driver Code Ends

function minCutCost(n, cuts) {

    // Add boundaries 0 and n to represent stick ends
    cuts.push(0);
    cuts.push(n);

    // Sort to ensure segments are in proper order
    cuts.sort((a, b) => a - b);

    const sz = cuts.length;
    const dp = Array.from({ length: sz }, () => Array(sz).fill(0));

    for (let len = 2; len < sz; len++) {
        for (let left = 0; left + len < sz; left++) {
            const right = left + len;
            let minCost = Number.MAX_SAFE_INTEGER;

            // Explore all possible cuts between left and right
            for (let i = left + 1; i < right; i++) {
                const cost = cuts[right] - cuts[left] + dp[left][i] + dp[i][right];
                minCost = Math.min(minCost, cost);
            }

            // Store the minimum cost for this segment
            dp[left][right] = (minCost === Number.MAX_SAFE_INTEGER) ? 0 : minCost;
        }
    }

    // Final result is the cost to cut the full stick (0 to sz - 1)
    return dp[0][sz - 1];
}



//Driver Code Starts
// Driver Code
const n = 10;
const cuts = [2, 4, 7];
console.log(minCutCost(n, cuts));

//Driver Code Ends

20

Time complexity: O(k³), where k is the number of cuts.
Auxiliary Space: O(k²)

Why Space Optimization Is Not Possible in This Problem?

In most Dynamic Programming problems, we can often reduce space complexity by observing that the current state only depends on a limited number of previous states. This allows us to reuse memory - keeping only one or two previous rows instead of the entire DP table. However, in this problem, the dependency pattern is fundamentally different. Each state dp[left][right] represents the minimum cost to cut the stick between cuts[left] and cuts[right]. To compute this value, we must explore all possible cuts between left and right, and for every possible cut position i, we rely on two non-adjacent subproblems — dp[left][i] and dp[i][right].
This means:

• There is no fixed transition direction (like top-down or left-right).
• Each state can depend on many scattered intervals that are spread across the DP table.
• These dependencies can overlap in unpredictable patterns, making it impossible to safely overwrite previous results.

Because of this complex interval dependency, we cannot discard previously computed values or compress the DP table into fewer rows/columns without losing essential data required for future calculations.