#.10 Write program to implement Dynamic Programming algorithm for the Optimal Binary Search Tree Problem.

import sys

def optimal_bst(keys, freq, n):
   
    cost = [[0 for _ in range(n)] for _ in range(n)]
    
    
    weight = [[0 for _ in range(n)] for _ in range(n)]
    
   
    for i in range(n):
        cost[i][i] = freq[i]
        weight[i][i] = freq[i]
    
   
    for length in range(2, n + 1):   
        for i in range(n - length + 1):
            j = i + length - 1
            cost[i][j] = sys.maxsize  
            weight[i][j] = weight[i][j - 1] + freq[j]  
            
           
            for r in range(i, j + 1):
                 
                left_cost = cost[i][r - 1] if r > i else 0
                right_cost = cost[r + 1][j] if r < j else 0
                total_cost = left_cost + right_cost + weight[i][j]
                
                
                if total_cost < cost[i][j]:
                    cost[i][j] = total_cost
    
    return cost[0][n - 1]  

# Example usage
keys = [10, 12, 20]  # Keys in sorted order
freq = [34, 8, 50]   # Frequency of each key
n = len(keys)

min_cost = optimal_bst(keys, freq, n)
print("The minimum cost of constructing an Optimal Binary Search Tree is:", min_cost)