#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/dynamic-programming/d-c-and-knuth-optimization/optimal-bst-implementation

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░██████████████████████████████████████████████████████████████████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/dynamic-programming/d-c-and-knuth-optimization/optimal-bst-implementation

Repovive

Optimal BST - Implementation - D&C and Knuth Optimization | Dynamic Programming | Repovive

Repovive.

Dynamic Programming21 sections · 918 units60h total

Open in Course

Optimal BST - Implementation

The code

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: $O(n^2)$ . Space complexity: $O(n^2)$ in time and $O(n)$ in space.