1644. Cheapest Lookup Tree
A dictionary stores the keys 0..n-1 in a binary search tree, and you know that key i will be looked up freq[i] times. Looking up a key costs the number of nodes on the path from the root down to it, so the root has depth 1, its children depth 2, and so on. The tree you build must contain every key exactly once and obey the search-tree order (smaller keys to the left).
The total cost of a tree is the sum over all keys of freq[i] times the depth of key i. Return the smallest possible total cost over all such trees as a 64-bit integer.
A cubic interval DP over all roots is too slow here. Use prefix sums for the weight of an interval and restrict each interval's root to the range between the best roots of its two sub-intervals, which gives O(n^2) time and O(n^2) space.
Example 1
- Input:
- freq = [4,2,6,3]
- Output:
- 26
- Explanation:
Rooting the tree at key 2 with key 0 (and key 1 below it) on the left and key 3 on the right costs 6 + 2*4 + 3*2 + 3*2 = 26, which is the minimum
Example 2
- Input:
- freq = [5]
- Output:
- 5
- Explanation:
A single key sits at the root at depth 1, costing 5 * 1.
Example 3
- Input:
- freq = [1,1,1,1,1,1,1]
- Output:
- 17
- Explanation:
Seven equal keys fit in a perfectly balanced tree: depths 1, 2, 2, 3, 3, 3, 3 add up to 17.
Constraints
1 ≤ n ≤ 800, where n = freq.length
0 ≤ freq[i] ≤ 106
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,600 msC++ 400 msJava 800 msJavaScript 800 msTypeScript 800 ms
Expected complexity
- Time
- O(n^2)
- Space
- O(n^2)