# Optimal Binary Search Tree

#### Try First, Check Solution later

1. You should first read the question and watch the question video.
2. Think of a solution approach, then try and submit the question on editor tab.
3. We strongly advise you to watch the solution video for prescribed approach.

`1. You are given two arrays -      The first array(keys), which is sorted and has distinct integers, represents search keys.   Second one(freq) represents frequency counts, where freq[i] is the number of searches to keys[i].2. A binary search tree is constructed containing all keys and the total cost of searches is minimum. 3. The cost of a BST node is the level of that node multiplied by its frequency.4. You have to find the minimum cost of all searches.`
Input Format
`A number Na1a2.. N integersb1b2.. N numbers`
Output Format
`Check the sample output and question video.`
Question Video
Constraints
`1 <= N <= 10001 <= keys[i],freq[i] <= 1000`
Sample Input
`91345678911364873747`
Sample Output
`125`

• Related Topics

Run

Run
Id Name