Minimum Cost to Cut a Stick LeetCode solution in Python

1
class Solution:
2
    def minCost(self, n: int, cuts: List[int]) -> int:
3
        cuts = [0] + sorted(cuts) + [n]
4
        k = len(cuts)
5
        dp = [[float("inf")] * k for _ in range(k)]
6
        for l in range(1, k + 1):
7
            for beg in range(k - l):
8
                end = beg + l
9
                if l == 1:
10
                    dp[beg][end] = 0
11
                    continue
12
                for i in range(beg + 1, end):
13
                    currcost = cuts[end] - cuts[beg]
14
                    currcost += dp[beg][i] + dp[i][end]
15
                    dp[beg][end] = min(dp[beg][end], currcost)
16
        return dp[0][k - 1]