23.05.28 Today’s Leetcode

1547. Minimum Cost to Cut a Stick (hard)

from collections import defaultdict

class Solution:
    def minCost(self, n: int, cuts: List[int]) -> int:
        def dfs(start, end):
            if (start, end) in cache:
                return cache[(start, end)]
            min_val = float('inf')
            cut_found = False
            for c in cuts:
                if c > start and c < end: # Important!!! check the boundary condition
                    left_val = dfs(start, c)
                    right_val = dfs(c, end)
                    min_val = min(min_val, left_val + right_val)
                    cut_found = True
                
            if not cut_found: # If no cut is found we know that the stick cannot be split more
                cache[(start, end)] = 0
            else:
                cache[(start, end)] = end - start + min_val
            return cache[(start, end)]

        cache = defaultdict(int)
        return dfs(0, n)

class Solution:
    def minCost(self, n, cuts):
        cuts.append(0)
        cuts.append(n)
        cuts.sort()
        m = len(cuts)
        dp = [[0] * m for _ in range(m)]

        for l in range(2, m):
            for i in range(m - l):
                j = i + l
                dp[i][j] = float('inf')
                for k in range(i + 1, j):
                    dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j] + cuts[j] - cuts[i])

        return dp[0][m - 1]