최적 이진 검색 트리

문제

$N$개의 키가 정렬된 상태로 주어지고, 각 키를 탐색할 빈도(가중치)가 주어진다. 이 키들로 이진 검색 트리를 구성할 때, 기대 비교 횟수를 최소화하는 최적 탐색 비용을 구하라.

여기서 탐색 비용은 $\sum_{i=1}^{N} (d_i \times w_i)$로 정의된다. 는 트리의 루트에서 번째 키까지의 깊이(루트의 깊이는 1)이며, 는 해당 키의 탐색 빈도다. 즉, 각 키의 트리 내 깊이와 탐색 빈도를 곱한 값들의 합을 최소로 만들어야 한다.