331. Optimal Binary Search Tree

Given n distinct keys in sorted order and the search frequency of each key, build a binary search tree over exactly those keys that minimizes the total search cost, where the cost of searching for a key is its frequency multiplied by its depth in the tree (the root is at depth 1). Print that minimum total cost.

Input: Three lines: n; n space-separated sorted keys; n space-separated frequencies (one per key). Output: Print a single integer - the minimum total search cost of the optimal BST.

1 <= n <= 500

Precomputing PREFIX SUMS of frequency is a small but meaningful optimization - without it, computing the range-sum term for every (i,j,r) triple would cost an additional O(n), pushing the total complexity to O(n⁴) instead of O(n³).

Build a binary search tree over given keys and frequencies to minimize the total weighted search cost. Brute force: Try every possible BST SHAPE over the given keys directly and compute each one's total weighted cost - the number of possible BST shapes grows combinatorially (related to Catalan numbers), impractical for larger n. Optimised: The interval DP recognizes that once a ROOT is chosen for a range, the LEFT and RIGHT sub-ranges become INDEPENDENT optimal sub-problems (since a BST's structure over a contiguous key range only depends on that range) - trying every possible root and taking the best, while reusing already-computed smaller sub-range optimal costs, avoids re-deriving the same sub-tree's cost repeatedly.

The brute-force recursion only depends on the pair (i, j) defining the subrange, so store each computed cost[i][j] in a table and reuse it whenever the same subrange is needed again (either via top-down memoization or bottom-up filling by increasing range length). Precomputing prefix sums of frequencies lets the frequency sum over any range be fetched in O(1) instead of resumming it each time. With O(n^2) distinct subranges and O(n) choices of root to try for each, this brings the total work down to a manageable cubic polynomial instead of exponential. Time: O(n^3) Space: O(n^2)

For every contiguous range of keys [i, j], try making each key k in that range the root, recursively compute the optimal cost of the left part [i, k-1] and right part [k+1, j], and add the sum of all frequencies in [i, j] (since every key one level below the root has its depth increased by one). Take the minimum over all choices of k. Implemented as plain recursion with no memoization, the same subranges are recomputed enormous numbers of times, giving Catalan-number-like exponential growth in the number of calls. Time: O(4^n / n^1.5) (exponential) Space: O(n)

Build on the same O(n^3) DP, but exploit a known monotonicity property of this specific problem: the optimal root index for range [i,j], call it root[i][j], always satisfies root[i][j-1] <= root[i][j] <= root[i+1][j]. This means when computing cost[i][j], you don't need to try every possible root from i to j - only the narrower range between the already-known optimal roots of two related, smaller subproblems. This 'Knuth-Yao speedup' cuts the total work from cubic to quadratic while still finding the exact same minimum-cost tree. Time: O(n^2) Space: O(n^2)

1. dp[i][j] = minimum search cost for a BST built over keys i..j alone. 2. Try every key r in [i,j] as the ROOT of that sub-range: cost = dp[i][r-1] + dp[r+1][j] + (sum of frequencies from i to j) - the sum-of-frequencies term accounts for every key in the range dropping ONE LEVEL DEEPER because of this root choice. 3. dp[i][j] = the minimum of that cost over every choice of root r; precompute prefix sums of frequency so the range-sum term is O(1) per (i,j,r) triple.

Time: O(n³) - for each of the O(n²) sub-ranges, trying every possible root costs O(n) (or O(n) with the prefix-sum optimization for the frequency-sum term, avoiding an additional inner loop). Space: O(n²), for the dp table and the prefix-sum array.

Test n = 1 (cost is simply that key's frequency times depth 1) and n = 500 (upper bound) for the O(n^3) interval DP's performance.

Be ready to explain the sum-of-frequencies term precisely - it accounts for the fact that EVERY key in the current range, not just the root, gets pushed one level deeper by the choice of root, adding exactly one extra frequency-weighted depth unit to the total cost.