Minimum Cost Tree From Leaf Values: DP Trên Mảng Tìm Cây Chi Phí Tối Thiểu

Đề bài: Cho mảng arr số dương. Xây cây nhị phân sao cho:

• Leaf nodes (inorder) = arr.
• Non-leaf node value = max leaf left subtree × max leaf right subtree.
• Minimize tổng giá trị non-leaf nodes.

Ví dụ: [6,2,4] → 2 cây khả thi, min cost = 32.

DP: dp[i][j] = min cost cho subarray arr[i..j]

• Base: dp[i][i] = 0 (leaf đơn lẻ, không có non-leaf).
• Transition: thử mọi k chia [i..j] thành [i..k] và [k+1..j]: dp[i][j] = min(dp[i][k] + dp[k+1][j] + max(arr[i..k]) * max(arr[k+1..j]))
• Kết quả: dp[0][n-1].

Code Python (Memoization + Optimization)

class Solution:
    def mctFromLeafValues(self, arr: list[int]) -> int:
        n = len(arr)
        # Precompute max for all ranges O(n^2)
        max_range = [[0]*n for _ in range(n)]
        for i in range(n):
            max_range[i][i] = arr[i]
            for j in range(i+1, n):
                max_range[i][j] = max(max_range[i][j-1], arr[j])
        
        from functools import lru_cache
        
        @lru_cache(None)
        def dp(i, j):
            if i >= j:
                return 0
            res = float('inf')
            for k in range(i, j):
                cost = dp(i, k) + dp(k+1, j) + max_range[i][k] * max_range[k+1][j]
                res = min(res, cost)
            return res
        
        return dp(0, n-1)

# Test
ob = Solution()
print(ob.mctFromLeafValues([6,2,4]))  # 32
print(ob.mctFromLeafValues([4,11]))   # 44

Tối ưu O(n) Stack Monotonic (Advanced)

Quan sát: luôn pair leaf nhỏ với neighbor nhỏ nhất có thể. Dùng stack giảm dần:

def mctFromLeafValues(self, arr):
    stack = [float('inf')]
    res = 0
    for a in arr:
        while stack[-1] <= a:
            mid = stack.pop()
            res += mid * min(stack[-1], a)
        stack.append(a)
    # Clean up stack
    while len(stack) > 2:
        res += stack.pop() * stack[-1]
    return res

Phân tích

Kết luận

DP là giải pháp tự nhiên, dễ implement. Monotonic stack O(n) rất tối ưu nhưng cần insight sâu. Interview thường chấp nhận DP O(n³) với n ≤ 40 (constraints LeetCode).