Minimum Cost to cut the stick

Practice Link

Given a wooden stick of length n units. The stick is labelled from 0 to n. For example, a stick of length 6 is labelled as follows:

Given an integer array cuts where cuts[i] denotes a position you should perform a cut at.

You should perform the cuts in order, you can change the order of the cuts as you wish.

The cost of one cut is the length of the stick to be cut, the total cost is the sum of costs of all cuts. When you cut a stick, it will be split into two smaller sticks (i.e. the sum of their lengths is the length of the stick before the cut). Please refer to the first example for a better explanation.

Return the minimum total cost of the cuts.

Intiution#

• We have to find the minimum cost of cutting my trying different orders to cut.

• Once the cut has been made, the partitions can be solved independently only if the cuts are sorted. -> We will sort the array.

• To calculate the (cost)length of stick before cut, we will make a little modification. We will add 0 and length of stick after. So that we can do: cost = cuts[j+1] - cuts[i-1]

• current ans = (cuts[j+1] - cuts[i-1]) + f(i, idx-1) + f(idx+1, j)

Recursive Solution (with Memoization)#

This is a partition DP problem. After sorting and padding cuts with 0 and n, the sub-range [i, j] represents the cut points we still need to make. For each candidate cut idx in [i, j], the cost is the current stick length (cuts[j+1] - cuts[i-1]) plus the cost of recursively handling the left and right sub-ranges. We try all idx and take the minimum, caching results in memo[i][j] to avoid recomputation. There are O(n^2) sub-ranges and each loops over O(n) cut candidates, giving O(n^3) without caching — memoization collapses this to O(n^2) unique states.

class Solution {
public:

    int solveCost(vector<int> &cuts, int i, int j, vector<vector<int>> &memo)
    {
        if(i>j)
            return 0;
        
        if(memo[i][j] != -1)
            return memo[i][j];
        
        int miniCost = INT_MAX;
        for(int idx = i; idx<=j; idx++)
        {
            int cost = (cuts[j+1] - cuts[i-1]) + solveCost(cuts, i, idx-1, memo) + solveCost(cuts, idx+1, j, memo);
            miniCost = min(miniCost, cost);
        }
        return memo[i][j] = miniCost;
    }

    int minCost(int n, vector<int>& cuts) {
        int c = cuts.size();
        cuts.insert(cuts.begin(), 0);
        cuts.push_back(n);
        sort(cuts.begin(), cuts.end());

        vector<vector<int>> memo(c+2, vector<int>(c+2, -1));

        return solveCost(cuts, 1, cuts.size()-2, memo);
    }
};

Time Complexity - O(n^2), where n-> size of cuts array

Space Complexity - O(n^2)

Tabulation Approach#

Convert the top-down memoized solution into a bottom-up fill. We iterate i from c down to 1 and j from 1 up to c, filling dp[i][j] using already-computed smaller sub-ranges. The iteration order ensures that dp[i][idx-1] and dp[idx+1][j] are always available when needed. This eliminates the recursion stack while keeping the same O(n^2) time and space.

class Solution {
public:
    int minCost(int n, vector<int>& cuts) {
        int c = cuts.size();
        cuts.insert(cuts.begin(), 0);
        cuts.push_back(n);
        sort(cuts.begin(), cuts.end());

        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;
                else{
                    int miniCost = INT_MAX;
                    for(int idx = i; idx<=j; idx++)
                    {
                        int cost = (cuts[j+1] - cuts[i-1]) + dp[i][idx-1] + dp[idx+1][j];
                        miniCost = min(miniCost, cost);
                    }
                    dp[i][j] = miniCost;
                }
            }
        }

        return dp[1][c];
    }
};