Dynamic Programming

Optimal Binary Search Tree

Introduced to me in CS341.

Problem Setup

Input:

• integers (or something else) $1,\dots ,n$
• probabilities of access $p_1,\dots ,p_n$ with $p_1+\cdots +p_n=1$ Output:
• an optimal BST with keys $1,\dots ,n$
• optimal: minimizes ${\sum }_{i=1}^n{p}_i\cdot (depth(i)+1)$ = expected number of tests for a search

The difficult part is coming up with the recurrence relation.

$M[i,j]=argmi{n}_k(M[i,k-1]+M[k+1,j])+{\sum }_{l=i}^j{p}_l$

• the sum can easily be precomputed with a prefix sum