Problem Statement in English

You’re given a wooden stick of length n units. The stick is labeled from 0 to n.

You are also given an integer array cuts where cuts[i] denotes a position you should perform a cut at. You can perform the cuts in any order.

The cost of making a cut at position x is equal to the length of the stick being cut. After you perform a cut, the stick is split into two smaller sticks (i.e., the left and right parts of the stick).

You need to determine the minimum total cost to perform all the cuts.

Approach

To solve the problem of finding the minimum cost to cut a stick at specified positions, we can use a dynamic programming approach with memoization.

The idea is to recursively calculate the cost of making cuts between two endpoints of the stick while considering all possible cut positions within that range.

For each range that we have, we iterate over all possible cuts that can be made within that range. For each cut, we calculate the cost of making that cut (which is the length of the stick being cut) plus the cost of cutting the left and right segments recursively. We keep track of the minimum cost found for each range.

It’s honestly not that bad.

Solution in Python


class Solution:
    def minCost(self, n: int, cuts: List[int]) -> int:
        
        @cache
        def dfs(l, r):
            if r - l == 1:
                return 0

            res = inf

            for cut in cuts:
                if l < cut < r:
                    res = min(res, (r - l) + dfs(l, cut) + dfs(cut, r))

            return 0 if res == inf else res

        return dfs(0, n)

Complexity

  • Time: $O(N^2 \times M)$
    Where N is the length of the stick and M is the number of cuts. The intuition is that the main function is trying every possible pair of points on the stick. This gives us the $O(N^2)$ factor. This comes from $\binom{N}{2}$ (roughly $N \times (N - 1)$ just for a quick and dirty number) possible pairs.

    For each pair, we are iterating through all the cuts to find the optimal cut point, which yields the $O(M)$ factor.

  • Space: $O(N^2)$
    Since we are using memoization to store the results of subproblems, we may end up storing results for every possible pair of points on the stick. This leads to a space complexity of $O(N^2)$.

Mistakes I Made

Yea I didn’t return $0$ifres` was inf initially. Gah

And we are done.