Question
Given an array arr of positive integers, consider all binary trees such that:
•
Each node has either 0 or 2 children;
•
The values of arr correspond to the values of each leaf in an in-order traversal of the tree.
•
The value of each non-leaf node is equal to the product of the largest leaf value in its left and right subtree, respectively.
Among all possible binary trees considered, return the smallest possible sum of the values of each non-leaf node. It is guaranteed this sum fits into a 32-bit integer.
A node is a leaf if and only if it has zero children.
Example 1:
Input: arr = [6,2,4]
Output: 32
Explanation: There are two possible trees shown.
The first has a non-leaf node sum 36, and the second has non-leaf node sum 32.
Plain Text
복사
Example 2:
Input: arr = [4,11]
Output: 44
Plain Text
복사
Constraints:
•
2 <= arr.length <= 40
•
1 <= arr[i] <= 15
•
It is guaranteed that the answer fits into a 32-bit signed integer (i.e., it is less than 2).
31
My Answer
class Solution:
def mctFromLeafValues(self, arr: List[int]) -> int:
# leaf가 아닌 노드는 subtree의 왼쪽과 오른쪽 subtree에서 가장 큰 값의 곱
# 노드들의 sum을 리턴하기 가능성이 여러개면 가장 작은것
# 각 노드는 0혹은 2개의 children만 가짐
# arr에 있는 값은 노드를 중위순회할때의 leaf들의 값
# 왼쪽자식 - 루트 - 오른쪽자식 순
n = len(arr)
dp = [[0]* n for _ in range(n)]
max_matrix = [[0] * n for _ in range(n)]
for start in range(n-1, -1, -1):
max_matrix[start][start] = arr[start]
for end in range(start+1, n):
max_matrix[start][end] = max(max_matrix[start][end - 1], arr[end])
dp[start][end] = float('inf')
for k in range(start, end):
dp[start][end] = min(dp[start][end], dp[start][k] + dp[k+1][end] + max_matrix[start][k] * max_matrix[k+1][end])
return dp[0][n-1]
Python
복사
Time Complexity: O(N^3)
Constraint이 40까지라서 충분히 가능
Optimized Version
class Solution:
def mctFromLeafValues(self, arr: List[int]) -> int:
stack = [float('inf')]
total = 0
for num in arr:
while stack[-1] <= num:
mid = stack.pop()
total += mid * min(stack[-1], num)
stack.append(num)
# 스택에 남은 값들 처리 (큰 값들 남음)
while len(stack) > 2:
total += stack.pop() * stack[-1]
return total
Python
복사
Time Complexity: O(N)
스택을 활용한 그리디 알고리즘
•
스택을 이용해 점점 커지는 수열을 유지한다.
•
현재 값이 스택 top보다 작거나 같을 때까지 pop하면서 계산을 수행한다.
•
pop한 값(mid)은 반드시 사라지기 때문에,
◦
mid * min(left, right)을 비용으로 추가.
•
마지막엔 스택에 남은 값들끼리 곱해서 마무리.
