// optimal binary search tree
// 3 Aug 2005

// data from Somchai P. Design & A. Algo pp.184-187

N = 8
pp = array (N * N)
c = array (N * N)
p = array N
inf = 99999

to set ar i j v  =  ar[i*N + j] = v

// protect access out of bound return 0
// and lower triangular return 0
to get ar i j = 
  if i > j 0
  else if j >= N 0
  else ar[i*N + j]

to initpp n | i j =
  for i 1 n
    set pp i i p[i]
  for i 1 n-1
    for j i+1 n
      set pp i j (get pp i j-1) + p[j]

to bst p n | i j k m nc =
  initpp n

//  for i 1 n
//    set c i i-1 0

  for k 1 n
    for i 1 n-k+1
      j = i+k-1
      set c i j inf
      for m i j
        nc = (get c i m-1) + (get c m+1 j) + (get pp i j)
        if nc < (get c i j)
          set c i j nc
  get c 1 n

// memoised version
to bstm2 i j | m nc =
  if (get c i j) == 0 
    set c i j inf
    for m i j
      nc = (bstm2 i m-1) + (bstm2 m+1 j) + (get pp i j)
      if nc < (get c i j)  
        set c i j nc
  get c i j

to bstm p n | k i j m nc =
  initpp n
  bstm2 1 n  

to pr ar n | i j =
  for i 1 n
    for j 1 n
      print get ar i j space
    nl

to main =
  p[1] = 22
  p[2] = 18
  p[3] = 20
  p[4] = 5
  p[5] = 25
  p[6] = 2
  p[7] = 8
  print bst p 7 nl
  pr c 7
  print bstm p 7 nl

main