题目描述:
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]