Problem statement

https://binarysearch.com/problems/Minimum-Parsing-Tree/

Solution

It is almost the same as 1547. Minimum Cost to Cut a Stick. The idea is to use dp on intervals

Complexity

Time complexity is O(n^3), which suprisingly pass all the tests

Code

class Solution:
    def solve(self, cuts):
        m = len(cuts)
        if m == 0: return 0
        nums = [j-i for i,j in zip(cuts, cuts[1:])]
        
        @lru_cache(None)
        def dfs(i, j):
            if i == j: return 0
            return min(dfs(i, l) + dfs(l+1, j) for l in range(i, j)) + sum(nums[i:j+1])
        
        return dfs(0, m - 2) + sum(nums)

Solution 2

There is also solution, using Knuth optimization, but I do not completely understand it.

Complexity

It is O(n^2)

Code

class Solution:
    def solve(self, cuts):
        m, INF = len(cuts), 10**10
        if m == 0: return 0

        dp = [[INF]* m for _ in range(m)]
        kp = [[None]* m for _ in range(m)]
        
        for length in range(2, m + 1):
            for i in range(0, m + 1 - length):
                j = i + length - 1
                base_cost = cuts[j] - cuts[i]
                
                if length == 2:
                    dp[i][j] = 0
                    continue

                if length == 3:
                    dp[i][j] = base_cost
                    kp[i][j] = i+1
                    continue
                    
                add_cost = INF

                for k in range(kp[i][j-1], kp[i+1][j] + 1):
                    if add_cost > dp[i][k] + dp[k][j] :
                        add_cost = dp[i][k] + dp[k][j]
                        kp[i][j] = k
                dp[i][j] = base_cost + add_cost

        return dp[0][-1] + cuts[-1] - cuts[0]