> ## Documentation Index
> Fetch the complete documentation index at: https://leetcode-py.wisl.dev/llms.txt
> Use this file to discover all available pages before exploring further.

> ## Agent Instructions
> leetcode-py is a Python LeetCode practice environment generator with one CLI: lcpy. It is not a service or platform.
> Each problem is a directory under leetcode/ with README.md, solution.py, test_solution.py, helpers.py, and playground.ipynb. lcpy gen creates them from JSON templates bundled with the package.
> Examples are backed by tests; copy them verbatim.

# Minimum Cost to Cut a Stick Python Solution

> Tested Python solution for LeetCode 1547 with 24 pytest cases. Generate a practice environment with lcpy.

LeetCode 1547, [Hard](/catalog/hard). Topics: [Array](/catalog/topics/array), [Dynamic Programming](/catalog/topics/dynamic-programming), [Sorting](/catalog/topics/sorting). [View on LeetCode](https://leetcode.com/problems/minimum-cost-to-cut-a-stick/description/).

Generate this problem as a practice environment: tested reference solution, 24 [parametrized pytest cases](/practice/testing), and a playground notebook:

```bash theme={"theme":{"light":"github-light","dark":"github-dark"}}
lcpy gen -n 1547   # by problem number
lcpy gen -s minimum_cost_to_cut_a_stick   # by problem name
```

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

![Stick labelled 0 to 6](https://assets.leetcode.com/uploads/2020/07/21/statement.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.

### Examples

![Example 1](https://assets.leetcode.com/uploads/2020/07/23/e1.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:
![Scenario](https://assets.leetcode.com/uploads/2020/07/21/e11.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).
```

```
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^6
* 1 \<= cuts.length \<= min(n - 1, 100)
* 1 \<= cuts\[i] \<= n - 1
* All the integers in `cuts` array are **distinct**.

## Solution

Reference implementation from [solution.py on GitHub](https://github.com/wislertt/leetcode-py/blob/main/leetcode/minimum_cost_to_cut_a_stick/solution.py), full suite in [test\_solution.py](https://github.com/wislertt/leetcode-py/blob/main/leetcode/minimum_cost_to_cut_a_stick/test_solution.py):

```python theme={"theme":{"light":"github-light","dark":"github-dark"}}
class Solution:
    # Time: O(m^3) where m = len(cuts)
    # Space: O(m^2)
    def min_cost(self, n: int, cuts: list[int]) -> int:
        bounds = sorted(cuts)
        prefix = [0, *bounds, n]
        m = len(prefix)
        # dp[i][j] = min cost to cut the segment (prefix[i], prefix[j]) entirely
        dp = [[0] * m for _ in range(m)]
        for length in range(2, m):
            for i in range(m - length):
                j = i + length
                dp[i][j] = min(dp[i][k] + dp[k][j] for k in range(i + 1, j)) + prefix[j] - prefix[i]
        return dp[0][m - 1]
```

## Complexity

| Time | Space |
| - | - |
| O(m^3) where m = len(cuts) | O(m^2) |

## Tags

[NeetCode All](/catalog/neetcode).


This documentation is built and hosted on [Mintlify](https://mintlify.com), a developer documentation platform.