leetcode146周赛-1130-叶值的最小代价生成树*

class Solution(object):
    def mctFromLeafValues(self, arr):
        """
        :type arr: List[int]
        :rtype: int
        """
        n = len(arr)
        f = {1: [0] * n}
        for l in range(2, n + 1):
            f[l] = [0] * n
            for i in range(n + 1 - l):
                f[l][i] = 1 << 31
                for k in range(1, l):
                    a = max(arr[i:i+k])
                    b = max(arr[i+k:i+l])
                    v = a * b + f[k][i] + f[l - k][i + k]
                    if v < f[l][i]:
                        f[l][i] = v
        return f[n][0]

class Solution(object):
    def mctFromLeafValues(self, arr):
        """
        :type arr: List[int]
        :rtype: int
        """
        n = len(arr)
        f = {1: [0] * n}
        for l in range(2, n + 1):
            f[l] = [0] * n
            for i in range(n + 1 - l):
                f[l][i] = 1 << 31
                for k in range(1, l):
                    a = max(arr[i:i+k])
                    b = max(arr[i+k:i+l])
                    v = a * b + f[k][i] + f[l - k][i + k]
                    if v < f[l][i]:
                        f[l][i] = v
        return f[n][0]