题目描述:
- 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]
来源: http://www.bubuko.com/infodetail-3133016.html