Minimum Cost Tree From Leaf Values LeetCode solution in Python

1
# Runtime: 472 ms (Top 12.37%) | Memory: 14 MB (Top 32.41%)
2
class Solution:
3
    def mctFromLeafValues(self, arr: List[int]) -> int:
4
        n = len(arr)
5
        d = {}
6

7
        def findMax(start, end):
8
            if (start, end) in d:
9
                return d[(start, end)]
10
            maxx = start
11
            for i in range(start + 1, end + 1):
12
                if arr[maxx] < arr[i]:
13
                    maxx = i
14
            d[(start, end)] = arr[maxx]
15
            return arr[maxx]
16

17
        dp = [[float("inf") for i in range(n)] for j in range(n)]
18
        for gap in range(n):
19
            for row in range(n - gap):
20
                col = row + gap
21
                if gap == 0:
22
                    dp[row][col] = 0
23
                elif gap == 1:
24
                    dp[row][col] = arr[row] * arr[col]
25
                else:
26
                    for k in range(row, col):
27
                        val = (
28
                            dp[row][k]
29
                            + findMax(row, k) * findMax(k + 1, col)
30
                            + dp[k + 1][col]
31
                        )
32
                        if val < dp[row][col]:
33
                            dp[row][col] = val
34

35
        return dp[0][-1]