Optimal BST - Implementation

Here's the Knuth-improved solution:

function optimalBST(n, freq)
    dp, opt := 2D (two-dimensional) arrays
    prefix := [0] + prefix_sums(freq)
    // Base cases
    for i from 1 to n:
        dp[i][i] := freq[i]
        opt[i][i] := i
    for i from 1 to n+1:
        dp[i][i-1] := 0
    // Fill by length
    for len from 2 to n
        for i from 1 to n - len + 1
            j := i + len - 1
            lo := opt[i][j-1] if j > i else i
            hi := opt[i+1][j] if i < n else j
            for k from lo to hi
                val := dp[i][k-1] + dp[k+1][j] + prefix[j] - prefix[i-1]
                if val < dp[i][j]:
                    dp[i][j] := val
                    opt[i][j] := k
    return dp[1][n]

Edge cases: when $j = i$ (single element), $lo = i$. When $i = n$, $hi = j$. The prefix sum avoids recomputing $\sum f_l$ each time.

Time complexity: $O(n^2)$ with Knuth optimization.

Space complexity: $O(n^2)$ for the dp and opt tables.