Roland's blog

Dr. Paul describes in his book the OptimalSearchTree algorithm. Here's it's implementation in ruby.

def print_matrix(m)
  print m.collect{|row| row.join("t")}.join("n") + "n"
end

def optimal_search_tree(p, q)
  n = p.size
  root = Array.new(n){Array.new(n){0}}
  a = Array.new(n){Array.new(n){0}}
  sigma = Array.new(n){Array.new(n){0}}
  for i in 0..(n-1)
    root[i][i] = i
    sigma[i][i] = p[i] + q[i] + q[i+1]
    a[i][i] = sigma[i][i]
  end
  for pass in 1..(n-1)
    for i in 0..(n-1-pass)
      j = i + pass
      sigma[i][j] = sigma[i][j-1] + p[j] + q[j+1]
      root[i][j] = i
      min = a[i+1][j]
      for k in (i+1)..j
        sum = a[i][k-1] + (a[k+1][j] rescue 0)
        if sum < min
          min = sum
          root[i][j] = k
        end
      end
      a[i][j] = min + sigma[i][j]
    end
  end
  [a, root, sigma]
end

And test out the functions:

p = [15, 10, 20, 30]
q = [5, 5, 0, 5, 10]
a, root, sigma = optimal_search_tree(p, q)
print_matrix a; print "n"
print_matrix root; print "n"
print_matrix sigma; print "n"

Results:

a:
25      50      110     195
0       15      55      135
0       0       25      90
0       0       0       45
root:
0       0       1       2
0       1       2       3
0       0       2       3
0       0       0       3
sigma:
25      35      60      100
0       15      40      80
0       0       25      65
0       0       0       45