Minimum Cost to Cut a Stick

Problem

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: (link)

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.

Example 1:

Input: n = 7, cuts = [1,3,4,5]
Output: 16
Explanation: Using cuts order = [1, 3, 4, 5] as in the input leads to the following scenario:

The first cut is done to a rod of length 7 so the cost is 7. The second cut is done to a rod of length 6 (i.e. the second part of the first cut), the third is done to a rod of length 4 and the last cut is to a rod of length 3. The total cost is 7 + 6 + 4 + 3 = 20.
Rearranging the cuts to be [3, 5, 1, 4] for example will lead to a scenario with total cost = 16 (as shown in the example photo 7 + 4 + 3 + 2 = 16).

Example 2:

Input: n = 9, cuts = [5,6,1,4,2]
Output: 22
Explanation: If you try the given cuts ordering the cost will be 25.
There are much ordering with total cost <= 25, for example, the order [4, 6, 5, 2, 1] has total cost = 22 which is the minimum possible.

Constraints:

• 2 <= n <= 10<sup>6</sup>

• 1 <= cuts.length <= min(n - 1, 100)

• 1 <= cuts[i] <= n - 1

• All the integers in cuts array are distinct.

Solution

This is an application of MCM logic.

• To explore all possible cuts efficiently, sort the given cuts in ascending order.

• Cut one at a time, explore all possible paths, and track the minimal cost.

• Treat the entire array as one block and cut it into two blocks using a partition index.

• The partition index will consider all possible cuts within the given block.

There are two components to consider:

1. Fixed Component: Before further cutting, the current length of the rod is added to the total cost.

2. Partition Blocks: Calculate the minimum length of each block after partitioning.

To determine the length of the current rod:

• Insert 0 at the beginning and the total length at the end of the array.

• When the rod is cut into two halves, the end position is where the cut occurs.

• By adding these two coordinates, you can determine the length of the rod at any given point.

Recursion

Time - O(Exponential)

Space - O(c), c-Total number of cuts

class Solution {
    private int f(int i, int j, List<Integer> cutsList){

        if(i>j) return 0;

        int ans = Integer.MAX_VALUE;
        for(int k=i; k<=j; k++){
            int fixedCost = cutsList.get(j+1) - cutsList.get(i-1);
            int totalCost = fixedCost 
                + f(i, k-1, cutsList)
                + f(k+1, j, cutsList);
            ans = Math.min(ans, totalCost);
        }

        return ans;
    }

    public int minCost(int n, int[] cuts) {
        List<Integer> cutsList = getSortedList(n, cuts);
        return f(1, cutsList.size()-2, cutsList);
    }

    private List<Integer>  getSortedList(int n, int[] cuts){
        List<Integer> cutsList = new ArrayList<>();
        cutsList.add(0);

        for(int x : cuts){
            cutsList.add(x);
        }

        cutsList.add(n);

        Collections.sort(cutsList);

        return cutsList;
    }
}

Memoization

Use a dp array of size (c+1, c+1) because when we cut the rod into the next half, we might exceed the index.

Time - O(cxcxc)

Space - O(cxc) + O(c)

class Solution {
    private int f(int i, int j, List<Integer> cutsList, int[][] dp){

        if(i>j) return 0;

        if(dp[i][j] != -1) return dp[i][j];

        int ans = Integer.MAX_VALUE;
        for(int k=i; k<=j; k++){
            int fixedCost = cutsList.get(j+1) - cutsList.get(i-1);
            int totalCost = fixedCost 
                + f(i, k-1, cutsList, dp)
                + f(k+1, j, cutsList, dp);
            ans = Math.min(ans, totalCost);
        }

        return dp[i][j] = ans;
    }

    public int minCost(int n, int[] cuts) {
        int c = cuts.length;
        int[][] dp = new int[c+1][c+1];
        for(int[] row : dp){
            Arrays.fill(row, -1);
        }

        List<Integer> cutsList = getSortedList(n, cuts);

        return f(1, cutsList.size()-2, cutsList, dp);
    }

    private List<Integer>  getSortedList(int n, int[] cuts){
        List<Integer> cutsList = new ArrayList<>();

        cutsList.add(0);
        for(int x : cuts){
            cutsList.add(x);
        }
        cutsList.add(n);

        Collections.sort(cutsList);
        return cutsList;
    }
}

Tabulation

Increment the dp size by 2

Time - O(cxcxc)

Space - O(cxc)

class Solution {

    public int minCost(int n, int[] cuts) {
        int c = cuts.length;
        int[][] dp = new int[c+2][c+2];
        List<Integer> cutsList = getSortedList(n, cuts);

        for(int i=c; i>=1; i--){
            for(int j=i; j<=c; j++){
                int ans = Integer.MAX_VALUE;
                for(int k=i; k<=j; k++){
                    int fixedCost = cutsList.get(j+1) - cutsList.get(i-1);
                    int totalCost = fixedCost 
                        + dp[i][k-1]
                        + dp[k+1][j];
                    ans = Math.min(ans, totalCost);
                }
                dp[i][j] = ans;
            }
        }

        return dp[1][c];
    }

    private List<Integer>  getSortedList(int n, int[] cuts){
        List<Integer> cutsList = new ArrayList<>();

        cutsList.add(0);
        for(int x : cuts){
            cutsList.add(x);
        }
        cutsList.add(n);

        Collections.sort(cutsList);
        return cutsList;
    }
}