1547. Minimum Cost to Cut a Stick - Explanation

1. Recursion

Intuition

Each cut costs the length of the current stick segment. The order of cuts matters because earlier cuts determine the lengths of segments for later cuts. We need to try all possible orderings of cuts and find the one with minimum total cost. For a segment from position l to r, we try each valid cut point, pay the segment length, then recursively solve the resulting sub-segments.

Algorithm

Define dfs(l, r) to return the minimum cost to make all cuts within the segment [l, r].
Base case: If r - l == 1, no cuts are possible, return 0.
For each cut point c between l and r:
- Calculate cost as (r - l) + dfs(l, c) + dfs(c, r).
- Track the minimum across all choices.
Return 0 if no cuts exist in the range, otherwise return the minimum cost.

class Solution:
    def minCost(self, n: int, cuts: List[int]) -> int:
        def dfs(l, r):
            if r - l == 1:
                return 0
            res = float("inf")
            for c in cuts:
                if l < c < r:
                    res = min(res, (r - l) + dfs(l, c) + dfs(c, r))
            res = 0 if res == float("inf") else res
            return res

        return dfs(0, n)

Time & Space Complexity

Time complexity: $O(m ^ N)$
Space complexity: $O(N)$ for recursion stack.

Where $m$ is the size of the $cuts$ array, $n$ is the length of the stick, and $N = min(n, m)$ .

2. Dynamic Programming (Top-Down) - I

Intuition

The recursive solution has overlapping subproblems since many segment pairs (l, r) are computed multiple times. By caching results for each unique (l, r) pair, we avoid redundant computation. The state depends only on the segment boundaries, not on how we arrived at that segment.

Algorithm

Create a memoization dictionary keyed by (l, r) pairs.
Define dfs(l, r) that returns cached results when available.
For each cut point in the range, compute the cost recursively.
Store and return the minimum cost for each segment.

class Solution:
    def minCost(self, n: int, cuts: List[int]) -> int:
        dp = {}

        def dfs(l, r):
            if r - l == 1:
                return 0
            if (l, r) in dp:
                return dp[(l, r)]

            res = float("inf")
            for c in cuts:
                if l < c < r:
                    res = min(res, (r - l) + dfs(l, c) + dfs(c, r))
            res = 0 if res == float("inf") else res
            dp[(l, r)] = res
            return res

        return dfs(0, n)

Time & Space Complexity

Time complexity: $O(m * N ^ 2)$
Space complexity: $O(N ^ 2)$

Where $m$ is the size of the $cuts$ array, $n$ is the length of the stick, and $N = min(n, m)$ .

3. Dynamic Programming (Top-Down) - II

Intuition

Instead of using arbitrary segment boundaries, we can index by cut positions. After sorting cuts, we define states by cut indices rather than positions. This reduces the state space from potentially O(n^2) to O(m^2) where m is the number of cuts. We pass indices i and j representing the range of cuts to consider, plus the actual segment boundaries l and r.

Algorithm

Sort the cuts array.
Create a 2D memoization table indexed by cut indices i and j.
Define dfs(l, r, i, j) where i to j are the cut indices within segment [l, r].
Base case: If i > j, no cuts in this range, return 0.
Try each cut index mid from i to j, recursively solve both sides.
Return the minimum cost.

class Solution:
    def minCost(self, n: int, cuts: List[int]) -> int:
        m = len(cuts)
        cuts.sort()
        dp = [[-1] * (m + 1) for _ in range(m + 1)]

        def dfs(l, r, i, j):
            if i > j:
                return 0
            if dp[i][j] != -1:
                return dp[i][j]

            res = float("inf")
            for mid in range(i, j + 1):
                cur = (r - l) + dfs(l, cuts[mid], i, mid - 1) + dfs(cuts[mid], r, mid + 1, j)
                res = min(res, cur)

            dp[i][j] = res
            return res

        return dfs(0, n, 0, m - 1)

Time & Space Complexity

Time complexity: $O(m\log m + m ^ 3)$
Space complexity: $O(m ^ 2)$

Where $m$ is the size of the $cuts$ array and $n$ is the length of the stick.

4. Dynamic Programming (Bottom-Up)

Intuition

We can solve this iteratively by building up from smaller segments to larger ones. First, add 0 and n as boundary points to the sorted cuts. Then dp[i][j] represents the minimum cost to cut the segment between cuts[i] and cuts[j]. We fill the table by increasing segment length, since longer segments depend on solutions for shorter ones.

Algorithm

Create extended cuts array: [0] + sorted(cuts) + [n].
Initialize a 2D DP table with zeros.
For each segment length from 2 to m+1:
- For each starting index i:
  - Set j = i + length.
  - Try each cut point mid between i and j.
  - dp[i][j] = min(cuts[j] - cuts[i] + dp[i][mid] + dp[mid][j]).
Return dp[0][m + 1].

class Solution:
    def minCost(self, n: int, cuts: List[int]) -> int:
        m = len(cuts)
        cuts = [0] + sorted(cuts) + [n]
        dp = [[0] * (m + 2) for _ in range(m + 2)]

        for length in range(2, m + 2):
            for i in range(m + 2 - length):
                j = i + length
                dp[i][j] = float("inf")
                for mid in range(i + 1, j):
                    dp[i][j] = min(
                        dp[i][j],
                        cuts[j] - cuts[i] + dp[i][mid] + dp[mid][j]
                    )

        return dp[0][m + 1]

Time & Space Complexity

Time complexity: $O(m\log m + m ^ 3)$
Space complexity: $O(m ^ 2)$

Where $m$ is the size of the $cuts$ array and $n$ is the length of the stick.