1547. Minimum Cost to Cut a Stick - Explanation

1. Recursion

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

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

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)

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.