Minimum Cost to Cut a Stick Python Solution

lcpy gen -n 1547   # by problem number
lcpy gen -s minimum_cost_to_cut_a_stick   # by problem name

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.

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]