# Minimum Cost to Cut a Stick
**Difficulty:** HARD
[External](https://leetcode.com/problems/minimum-cost-to-cut-a-stick)
Canonical: https://scaleengineer.com/dsa/problems/minimum-cost-to-cut-a-stick
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array
**Companies:** [PhonePe](https://scaleengineer.com/companies/phonepe), [LINE](https://scaleengineer.com/companies/line)
---
## 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:

![](https://assets.glich.co/dsa/minimum-cost-to-cut-a-stick/image0.jpg) 

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:**

![](https://assets.glich.co/dsa/minimum-cost-to-cut-a-stick/image1.jpg) 

**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:
![](https://assets.glich.co/dsa/minimum-cost-to-cut-a-stick/image2.jpg)
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 <= 106`
* `1 <= cuts.length <= min(n - 1, 100)`
* `1 <= cuts[i] <= n - 1`
* All the integers in `cuts` array are **distinct**.

# Approaches
## Brute-Force Recursion
This approach models the problem using a straightforward recursive function. The core idea is that for any piece of the stick, we can try making the first cut at any of the available cut points within that piece. The total cost for a chosen first cut is the length of the current stick piece plus the minimum costs for the resulting two smaller pieces. The function then explores all possible first cuts and returns the minimum cost among them.
**Time:** O(c * 2^c), where `c` is the number of cuts. The number of recursive calls grows exponentially because subproblems are recomputed. · **Space:** O(c) for the recursion call stack depth, where `c` is the number of cuts.
**Pros:** Simple to understand and implement.; Directly follows the problem's recursive structure.
**Cons:** Extremely inefficient due to massive redundant computations.; Will result in a 'Time Limit Exceeded' error for the given constraints.
### Explanation
First, we augment the `cuts` array by adding the stick's boundaries, `0` and `n`. We then sort this new array to process the cuts in a structured manner. Let's call this `new_cuts`.

We define a recursive function, say `solve(i, j)`, which computes the minimum cost to cut the stick segment defined by `new_cuts[i]` and `new_cuts[j]`.

The base case for the recursion is when there are no cuts to be made between `new_cuts[i]` and `new_cuts[j]`. This happens when `j` is `i + 1`. In this case, the cost is 0.

In the recursive step, for a segment from `new_cuts[i]` to `new_cuts[j]`, we iterate through all possible cut points `new_cuts[k]` where `i < k < j`. For each `k`, we consider it as the first cut.

The cost of making the first cut at `new_cuts[k]` is `(new_cuts[j] - new_cuts[i])`. After this cut, we have two independent subproblems: cutting the segment `(new_cuts[i], new_cuts[k])` and cutting the segment `(new_cuts[k], new_cuts[j])`.

The total cost for choosing `k` is `(new_cuts[j] - new_cuts[i]) + solve(i, k) + solve(k, j)`.

The function `solve(i, j)` returns the minimum of these costs over all possible `k`.

The final answer is obtained by calling `solve(0, m-1)`, where `m` is the size of `new_cuts`.

```java
import java.util.*;

class Solution {
    public int minCost(int n, int[] cuts) {
        List<Integer> allCuts = new ArrayList<>();
        for (int cut : cuts) {
            allCuts.add(cut);
        }
        allCuts.add(0);
        allCuts.add(n);
        Collections.sort(allCuts);
        return solve(0, allCuts.size() - 1, allCuts);
    }

    private int solve(int i, int j, List<Integer> allCuts) {
        if (j - i <= 1) {
            return 0;
        }

        int minCost = Integer.MAX_VALUE;
        for (int k = i + 1; k < j; k++) {
            int currentCost = (allCuts.get(j) - allCuts.get(i)) +
                              solve(i, k, allCuts) +
                              solve(k, j, allCuts);
            minCost = Math.min(minCost, currentCost);
        }
        return minCost;
    }
}
```
### Algorithm
*   Create a new list of cuts that includes `0` and `n`. Sort this list. Let's call it `new_cuts`.
*   Define a recursive function `solve(i, j)` which calculates the minimum cost to cut the stick between `new_cuts[i]` and `new_cuts[j]`.
*   In `solve(i, j)`:
    *   If `j <= i + 1`, it means there are no cuts to be made in this segment. Return `0`.
    *   Otherwise, initialize `min_cost` to infinity.
    *   Iterate `k` from `i + 1` to `j - 1`. For each `k`, we consider making a cut at `new_cuts[k]`.
    *   The cost for this choice of `k` is `(new_cuts[j] - new_cuts[i]) + solve(i, k) + solve(k, j)`.
    *   Update `min_cost = min(min_cost, current_cost)`.
    *   Return `min_cost`.
*   The initial call would be `solve(0, new_cuts.size() - 1)`.

## Recursion with Memoization (Top-Down DP)
This approach enhances the brute-force recursion by using memoization to avoid recomputing results for the same subproblems. We use a 2D array, `memo`, to store the minimum cost for cutting each possible stick segment. Before computing the cost for a segment, we check if it's already in our `memo` table. If so, we use the stored value; otherwise, we compute it, store it, and then return it.
**Time:** O(c^3), where `c` is the number of cuts. Let `m = c + 2`. There are `O(m^2)` subproblems `(i, j)`. Each subproblem takes `O(m)` time to solve (the loop for `k`). Since each subproblem is solved only once, the total time is `O(m^3)`. · **Space:** O(c^2) for the memoization table `memo`. The recursion stack depth adds `O(c)`. So, the total space is dominated by the memoization table, `O(c^2)`.
**Pros:** Much more efficient than brute-force.; Still relatively intuitive as it follows the recursive problem structure.; Sufficiently fast for the given constraints.
**Cons:** Has recursion overhead, which might make it slightly slower than a pure iterative DP solution.
### Explanation
The overall structure is the same as the recursive approach. We first create a sorted list of all cut points, including `0` and `n`.

We introduce a 2D array, `memo[m][m]`, where `m` is the number of points in our sorted list. This table will store the results of `solve(i, j)`. We initialize it with a sentinel value (e.g., -1) to indicate that a subproblem has not been solved yet.

The recursive function `solve(i, j)` is modified:
*   At the beginning of the function, it checks `memo[i][j]`. If the value is not the sentinel, it means we have already computed the result for this subproblem, so we return the stored value immediately.
*   If the value is the sentinel, we proceed with the computation as in the brute-force approach.
*   After computing the minimum cost, but before returning it, we store this value in `memo[i][j]`.

This simple addition of a lookup table drastically reduces the number of computations, changing the time complexity from exponential to polynomial.

```java
import java.util.*;

class Solution {
    public int minCost(int n, int[] cuts) {
        List<Integer> allCuts = new ArrayList<>();
        for (int cut : cuts) {
            allCuts.add(cut);
        }
        allCuts.add(0);
        allCuts.add(n);
        Collections.sort(allCuts);
        
        int m = allCuts.size();
        int[][] memo = new int[m][m];
        for (int[] row : memo) {
            Arrays.fill(row, -1);
        }
        
        return solve(0, m - 1, allCuts, memo);
    }

    private int solve(int i, int j, List<Integer> allCuts, int[][] memo) {
        if (j - i <= 1) {
            return 0;
        }
        if (memo[i][j] != -1) {
            return memo[i][j];
        }

        int minCost = Integer.MAX_VALUE;
        for (int k = i + 1; k < j; k++) {
            int currentCost = (allCuts.get(j) - allCuts.get(i)) +
                              solve(i, k, allCuts, memo) +
                              solve(k, j, allCuts, memo);
            minCost = Math.min(minCost, currentCost);
        }
        
        memo[i][j] = minCost;
        return minCost;
    }
}
```
### Algorithm
*   Create a list `allCuts` from the `cuts` array, add `0` and `n`, and sort it. Let `m` be its size.
*   Create a 2D memoization table `memo[m][m]` and initialize it with -1.
*   Define a recursive function `solve(i, j)`:
    *   If `j - i <= 1`, return 0.
    *   If `memo[i][j]` is not -1, return `memo[i][j]`.
    *   Initialize `minCost = Integer.MAX_VALUE`.
    *   For `k` from `i + 1` to `j - 1`:
        *   `currentCost = (allCuts.get(j) - allCuts.get(i)) + solve(i, k) + solve(k, j)`.
        *   `minCost = min(minCost, currentCost)`.
    *   Store `minCost` in `memo[i][j]`.
    *   Return `minCost`.
*   Call `solve(0, m - 1)`.

## Tabulation (Bottom-Up DP)
This is an iterative dynamic programming approach that builds the solution from the bottom up. Instead of starting from the main problem and breaking it down, we start by solving the smallest subproblems and use their solutions to solve progressively larger ones. This eliminates recursion and its associated overhead.
**Time:** O(c^3), where `c` is the number of cuts. Let `m = c + 2`. The three nested loops for `len`, `i`, and `k` result in a cubic time complexity. · **Space:** O(c^2) for the 2D DP table, where `c` is the number of cuts.
**Pros:** Most efficient approach among the three.; Avoids recursion overhead, potentially leading to better performance in practice compared to the memoized version.
**Cons:** Can be slightly less intuitive to formulate than the recursive top-down approach.
### Explanation
As before, we start by creating a sorted list `new_cuts` containing `0`, `n`, and all the given cuts. Let `m` be its size.

We use a 2D DP table, `dp[m][m]`, where `dp[i][j]` stores the minimum cost to cut the stick segment from `new_cuts[i]` to `new_cuts[j]`.

We iterate over the length of the segments, `len`, from 2 up to `m-1`. A segment of length `len` (in terms of indices) corresponds to a stick piece with `len-1` potential cuts inside.

For each `len`, we iterate through all possible starting indices `i` for a segment of that length. The ending index `j` is simply `i + len`.

For each `(i, j)` pair, we calculate `dp[i][j]`. The cost of the first cut on this segment is `new_cuts[j] - new_cuts[i]`. We need to find the best position `k` for this first cut (`i < k < j`). The total cost will be `(new_cuts[j] - new_cuts[i]) + dp[i][k] + dp[k][j]`. We find the minimum over all possible `k`.

The values `dp[i][k]` and `dp[k][j]` are already computed because they correspond to smaller segment lengths.

The final answer is stored in `dp[0][m-1]`, which represents the minimum cost for the original stick from `0` to `n`.

```java
import java.util.*;

class Solution {
    public int minCost(int n, int[] cuts) {
        List<Integer> allCuts = new ArrayList<>();
        for (int cut : cuts) {
            allCuts.add(cut);
        }
        allCuts.add(0);
        allCuts.add(n);
        Collections.sort(allCuts);
        
        int m = allCuts.size();
        int[][] dp = new int[m][m];

        for (int len = 2; len < m; len++) {
            for (int i = 0; i <= m - 1 - len; i++) {
                int j = i + len;
                dp[i][j] = Integer.MAX_VALUE;
                for (int k = i + 1; k < j; k++) {
                    int cost = (allCuts.get(j) - allCuts.get(i)) + dp[i][k] + dp[k][j];
                    dp[i][j] = Math.min(dp[i][j], cost);
                }
            }
        }
        
        return dp[0][m - 1];
    }
}
```
### Algorithm
*   Create a list `allCuts` from the `cuts` array, add `0` and `n`, and sort it. Let `m` be its size.
*   Create a 2D DP table `dp[m][m]`.
*   Iterate `len` from 2 to `m-1`.
*   Iterate `i` from 0 to `m - 1 - len`.
*   Let `j = i + len`.
*   Initialize `minSubproblemCost = Integer.MAX_VALUE`.
*   Iterate `k` from `i + 1` to `j - 1`.
*   `minSubproblemCost = min(minSubproblemCost, dp[i][k] + dp[k][j])`.
*   `dp[i][j] = (allCuts.get(j) - allCuts.get(i)) + minSubproblemCost`.
*   Return `dp[0][m-1]`.

# Solutions
### Java

```java
class Solution {
public
  int minCost(int n, int[] cuts) {
    List<Integer> nums = new ArrayList<>();
    for (int x : cuts) {
      nums.add(x);
    }
    nums.add(0);
    nums.add(n);
    Collections.sort(nums);
    int m = nums.size();
    int[][] f = new int[m][m];
    for (int l = 2; l < m; ++l) {
      for (int i = 0; i + l < m; ++i) {
        int j = i + l;
        f[i][j] = 1 << 30;
        for (int k = i + 1; k < j; ++k) {
          f[i][j] =
              Math.min(f[i][j], f[i][k] + f[k][j] + nums.get(j) - nums.get(i));
        }
      }
    }
    return f[0][m - 1];
  }
}

```

### CPP

```cpp
class Solution {
public:
  int minCost(int n, vector<int> &cuts) {
    cuts.push_back(0);
    cuts.push_back(n);
    sort(cuts.begin(), cuts.end());
    int m = cuts.size();
    int f[110][110]{};
    for (int l = 2; l < m; ++l) {
      for (int i = 0; i + l < m; ++i) {
        int j = i + l;
        f[i][j] = 1 << 30;
        for (int k = i + 1; k < j; ++k) {
          f[i][j] = min(f[i][j], f[i][k] + f[k][j] + cuts[j] - cuts[i]);
        }
      }
    }
    return f[0][m - 1];
  }
};

```

### Python

```python
class Solution:
    def minCost(self, n: int, cuts: List[int]) -> int: cuts . extend([0, n]) cuts . sort() m = len(cuts) f = [[0] * m for _ in range(m)] for l in range(2, m): for i in range(m - l): j = i + l f[i][j] = inf for k in range(i + 1, j): f[i][j] = min(f[i][j], f[i][k] + f[k][j] + cuts[j] - cuts[i]) return f[0][- 1]

```