Minimum Cost to Cut a Stick — LeetCode 1547 Python Solution

The problem

Given a wooden stick of length n units. The stick is labelled from 0 to n.

Example

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:

Python solution

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]

Complexity

Pattern: Sorting

Spend O(n log n) once to buy an ordering that makes the rest of the problem trivial. LeetCode 1547. Minimum Cost to Cut a Stick is filed here because LeetCode tags it Sorting, which is the vocabulary this hub collects.

The sorting guide has the Python template for the pattern and the 401 LeetCode problems that use it.

Related problems